91. Decode Ways

,

DFS + Cache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int numDecodings(String s) {
        Map<Integer, Integer> startIndexToCountMap = new HashMap<>();
        return dfs(startIndexToCountMap, s, 0);
    }

    private int dfs(Map<Integer, Integer> startIndexToCountMap, String s, int i) {
        if (i == s.length()) {
            return 1;
        }

        Integer cached = startIndexToCountMap.get(i);
        if (cached != null) {
            return cached;
        }

        int count = 0;
        char a = s.charAt(i);
        if (a == '0') {
            // ignore
        } else if (a == '1') {
            count += dfs(startIndexToCountMap, s, i + 1);
            if (i + 1 < s.length()) {
                count += dfs(startIndexToCountMap, s, i + 2);
            }
        } else if (a == '2') {
            count += dfs(startIndexToCountMap, s, i + 1);
            if (i + 1 < s.length() && s.charAt(i + 1) <= '6') {
                count += dfs(startIndexToCountMap, s, i + 2);
            }
        } else {
            count = dfs(startIndexToCountMap, s, i + 1);
        }

        startIndexToCountMap.put(i, count);
        return count;
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int numDecodings(String s) {
        // 定义 dp[i] 为前 i 个字符组成的字符串对应的解码方法数
        int[] dp = new int[s.length() + 1];
        dp[0] = 1; // 0 个字符时解码方法数为 1

        for (int j = 1; j <= s.length(); j++) {
            char c = s.charAt(j - 1);

            // 作为一个字符解码时
            if (c >= '1' && c <= '9') {
                dp[j] = dp[j - 1];
            }

            // 作为两个字符解码时
            if (j - 2 >= 0) {
                char prevChar = s.charAt(j - 2);
                if (prevChar == '1' || (prevChar == '2' && c <= '6')) {
                    dp[j] += dp[j - 2];
                }
            }
        }

        return dp[s.length()];
    }
}

References

91. Decode Ways