学步园

题目:

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方法。

首先，增加O（n）空间作为记录状态。不放增加w[]来记录，w[i]所对应的是当字符串到达第i个字符的时候的可能情况数。

而w[i]是如何得来的呢？想象一下，当只有一个数值的时候，比如‘2’，则只可能有一种，即2->B;

如果有两个数值的时候，比如’23‘，则可能是‘2’和‘3’->BC，也可能是‘23’->W.'2'和'3'是根据‘3’之前可能的情况*1决定的；而'23‘是根据’2‘之前的可能情况数*1决定的。

因此，w[1]=1,w[2]=2.下标1对应‘2’，2对应‘3’，因此该情况为1*w[1]；而w[0]则始终记为1；这样若是23符合条件，则1*w[0]即可。所以加起来为2种情况。

在一个例子：‘20’，则可能是‘2’和‘0’及‘20’两种情况。但是第一种，不存在‘0’的对应关系，所以，第一种情况为0*w[1]=0;第二种情况存在，所以为1*w[0] = 1;所以加起来为1种情况。

注意：一定要留意开头为‘0’的情况。一般x0x的情况和0x的情况。

AC代码：

public int numDecodings(String s) {
        if(s==null || s.isEmpty() ||s.charAt(0)=='0')
            return 0;
        char[] str = s.toCharArray();
        if(str.length==1)
            return str[0]=='0'?0:1;
        int[] w = new int[str.length + 1];
        w[0] = 1;
        w[1] = str[1]=='0'?0:1;
        for (int i=2;i<w.length;i++){
            char cur = str[i-1];
            int alone = 0;
            int dbl = 0;
            int rst = 0;
            if(cur!='0')
                alone = 1;
            int twoNum = Integer.parseInt(""+str[i-2]+cur);
            if(str[i-2]!='0' && twoNum>=1 && twoNum<=26){
                dbl = 1;
            }
            rst = alone*w[i-1]+dbl*w[i-2];
            w[i] = rst;
        }
        return w[w.length-1];
    }