Question
A message containing letters from AZ
is being encoded to numbers using the following mapping:
1 2 3 4
 'A' > 1 'B' > 2 ... 'Z' > 26

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

Solution
In this question, we have to try different length of string, such as one or two because the number belongs to 1 to 26.
Code
Brute force (DFS)
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
 public int numDecodings(String s) { if (s == null  s.length() == 0) return 0; return dfs(s, 0); } public int dfs(String s, int start) { if (start > s.length()) return 0; if (start == s.length()) return 1; int res = 0; if (start + 1 <= s.length()) { int oneNum = Integer.parseInt(s.substring(start, start + 1)); if (oneNum >= 0 && oneNum <= 9) { res += dfs(s, start + 1); } } if (start + 2 <= s.length()) { int twoNum = Integer.parseInt(s.substring(start, start + 2)); if (twoNum >= 10 && twoNum <= 26) { res += dfs(s, start + 2); } } return res; }

DFS + Memo
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
 public int numDecodings(String s) { int n = s.length(); if (s == null  n == 0) return 0; int[] memo = new int[n + 1]; Arrays.fill(memo, 1); return dfs(s, 0, memo); } public int dfs(String s, int start, int[] memo) { if (memo[start] != 1) return memo[start]; if (start > s.length()) return 0; if (start == s.length()) return 1; int res = 0; if (start + 1 <= s.length()) { int oneNum = Integer.parseInt(s.substring(start, start + 1)); if (oneNum >= 1 && oneNum <= 9) { res += dfs(s, start + 1, memo); } } if (start + 2 <= s.length()) { int twoNum = Integer.parseInt(s.substring(start, start + 2)); if (twoNum >= 10 && twoNum <= 26) { res += dfs(s, start + 2, memo); } } memo[start] = res; return memo[start]; }

Bottom up DP
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
 public int numDecodings(String s) { if (s == null  s.length() == 0) return 0; int n = s.length(); int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = s.charAt(0) == '0' ? 0 : 1; for (int i = 2; i <= n; i++) { int oneDigit = s.charAt(i  1)  '0'; int twoDigits = (s.charAt(i  2)  '0') * 10 + (s.charAt(i  1)  '0'); if (oneDigit > 0 && oneDigit <= 9) { dp[i] += dp[i  1]; } if (twoDigits >= 10 && twoDigits <= 26) { dp[i] += dp[i  2]; } } return dp[n]; }
