?
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.
分析：
定义d 为0~9中任意一个。
例如：137 -> ddd，或者也可以写为 137 -> 1d7。
定义F[i]表示S的子串S[0..i]的decode ways。
假设我们已经知道了F[0]~F[i]，现在需要求解F[i+1]。
先不考虑边界，就考虑一般情况：
1.S[i+1] == '0'，如果S[i]为'1'或者'2'，F[i+1] = F[i-1]，否则无解；
2.如果S[i]为'1'，F[i+1] = F[i] + F[i-1]（例如xxxxxx118，可以是xxxxxx11 + 8，也可以是xxxxxx1 + 18）；
3.如果S[i]为'2'，当S[i+1] <= '6'时，F[i+1] = F[i] + F[i-1] （最大的Z为26，272829不存在），当S[i+1] > '6'时，F[i+1] = F[i] （例如xxxxxx28，只能是xxxxxx2 + 8）。
上述分析参考地址：http://blog.csdn.net/pickless/article/details/11586039，本人略作修改。
源码：Java版本
算法分析：时间复杂度O(n)，空间复杂度O(n)
?
public class Solution {
public int numDecodings(String s) {
if(s==null || s.isEmpty() || s.charAt(0)=='0') {
return 0;
}
int n=s.length();
int[] f=new int[n+1];
f[0]=1;
f[1]=1;
for(int i=2;i
?
代码介绍：注意f[0]的初始值为1，而非0. 如对于字符串“11”,遇到第二个1的时候,f[2]=f[1]+f[0]，f[1]是等于1，f[0]的初始值也要为1.
注：上述代码的空间复杂度为O(n),其实也可用三个变量代替f[i-1],f[i],f[i+1]，时间复杂度会降为O(1).但使用数组思路会更加清晰。