91. Decode Ways

• Visit Leetcode problem

Problem

Approach

Implementation

1. Recursion

class Solution {
    // Chia thành các group 1 hoặc 2 phần tử
    // giải bằng Recursion (vẽ cây nhị phân ra giấy cho dễ hình dung) => TLE 
    // convert Recursion => DP => AC
    
    private String s;
    public int numDecodings(String s) {
        this.s = s;
        return dfs(0);
    }

    private int dfs(int startIdx) {
        // base case
        if (startIdx >= s.length()) {
            return 1;
        }

        int ans = 0;

        boolean isZero = (s.charAt(startIdx)-'0') == 0;

        // if s[i] = '0' 
        // => s[i] can not be in group with s[i+1] or stand alone
        if (isZero) {
            return 0;
        }

        // |i|i+1| is 2 group
        ans += dfs(startIdx + 1);

        // |(i)(i+1)| is 1 group
        if (startIdx+1 < s.length()) {
            int num = (s.charAt(startIdx)-'0') * 10 + (s.charAt(startIdx+1)-'0');
            if (num <= 26) {
                ans += dfs(startIdx+2);
            }
        }

        return ans;
    }
}

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n+1];
        dp[n] = 1;

        for (int i = s.length()-1; i >= 0; i--) {
            boolean isZero = (s.charAt(i)-'0') == 0;
            
            // if s[i] = '0' 
            // => s[i] can not be in group with s[i+1] or stand alone
            if (isZero) {
                dp[i] = 0;
                continue;
            }

            // |i|i+1| is 2 group
            dp[i] += dp[i+1];

            // |(i)(i+1)| is 1 group
            if (i+1 < s.length()) {
                int num = (s.charAt(i)-'0') * 10 + (s.charAt(i+1)-'0');
                if (num <= 26) {
                    dp[i] += dp[i+2];
                }
            }
        }

        return dp[0];
    }
}