91. Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1: Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). Example 2: Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

孩子只有两个可能，一个是一个字符的情况，另一个两个字符的情况。 一个字符时： 判断这个字符是否为‘0’， 不为0 就可以进入孩子，继续查找。 两个字符时： 判断这两个字符组成的数字是否在10 和 26 之间，如果是，可以进入孩子继续查找。

basecase：

当start处在最后一位时， 判断是否为 ‘0’ 为0返回0，为1返回1.当start超出了s的范围，返回1即可。

注意，此题目是DAG， 所以会有重复计算，使用一个map记录答案。当做缓存。 可以使用Integer[] 代替map， 为null 说明没有访问过，需要计算。不为null，直接返回答案即可。

class Solution { public int numDecodings(String s) { Integer[] results = new Integer[s.length() + 1]; return dfs(s, 0, results); } private int dfs(String s, int start, Integer[] results) { // 缓存 if (results[start] != null) { return results[start]; } // basecase if (start == s.length()) { results[start] = 1; return 1; } if (start == s.length() - 1) { if (s.charAt(start) == '0') { results[start] = 0; return 0; } else { results[start] = 1; return 1; } } int result = 0; if (s.charAt(start) != '0') { result += dfs(s, start + 1, results); } if (Integer.valueOf(s.substring(start, start + 2)) <= 26 && Integer.valueOf(s.substring(start, start + 2)) >= 10) { result += dfs(s, start + 2, results); } results[start] = result; return result; } }