LeetCode 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 an encoded message containing digits, determine the total number of ways to decode it.
For example,Given encoded message "12", it could be decoded as "AB"
(1 2) or "L" (12). The number of ways decoding "12" is 2.
又是一道可以回溯或是dp的题目，一开始按照回溯的思路，每次判断当前index的个位数与index,index+1对应的两位数，查看两种情况是否满足decode要求，即个位数在1-9之间，两位数在1-26之间。写完了以后LTE了。。。
写了1个半小时才改对dp的版本。。。真是无语了。。。
注意初始条件：
- 当长度小于什么时，应该直接返回？
- 应该初始化dp[0]和dp[1]吗？分别初始化成什么？
- 写出递推公式
这里有一个误区，真正的判断条件应该是：
个位数在1-9之间，两位数在10-26之间！！！
代码：
public class Solution {
public int numDecodings(String s) {
int n = s.length();
if (n <= 0) return 0;
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 first = Integer.valueOf(s.substring(i-1,i));
int second = Integer.valueOf(s.substring(i-2,i));
if (first >= 1 && first <= 9)
dp[i] += dp[i-1];
if (second >= 10 && second <= 26)
dp[i] += dp[i-2];
}
return dp[n];
}
}
