这道题，印象深刻，和小白讨论过。
方法是DP，关键点是“0”；
DP问题，从前往后还是从后往前？（我还是很烂的)
一般都是从后往前，个别情况例外。
自己写出来的code：
public class Solution {
public int numDecodings(String s) {
int len = s.length();
if (len==0) return 0;
int[] mem = new int[len+1];
mem[len] = 1;
mem[len-1] = (s.charAt(len-1)=='0')? 0 : 1;
for (int i=len-2; i>=0; i--) {
if(s.charAt(i) == '0') mem[i] = 0;
else
mem[i] = (Integer.parseInt(s.substring(i, i+2)) <= 26)? mem[i+1]+mem[i+2] : mem[i+1];
}
return mem[0];
}
}
答案代码和我自己写的竟然如此的像！！！！
长舒一口气。
public class Solution {
public int numDecodings(String s) {
int n = s.length();
if (n == 0) return 0;
int[] memo = new int[n+1];
memo[n] = 1;
memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0;
for (int i = n - 2; i >= 0; i--)
if (s.charAt(i) == '0') continue;
else memo[i] = (Integer.parseInt(s.substring(i,i+2))<=26) ? memo[i+1]+memo[i+2] : memo[i+1];
return memo[0];
}
}
Don't think about other things. Just keep working.
Working hard is the most beautiful moment.
Just keep concentrating on it. --- 10/19/2016
