leetcode-解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

1
2
3
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

1
2
3
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
考虑String字符串新加入一个char时的case；
两个维度：1:新加入的char是否为0；2:新加入的跟前一个字符表示的数字是否合法（1-26）
if(2){
	a[n]+=a[n-2];
	if(!1){
		a[n]+=a[n-1];
	}
}else{
	if(!1){
		a[n]+=a[n-1];
    }else{
    	return 0;//无法解码    
    }	
}
该题是爬楼梯问题的升级版，实质是相通的，都属于"斐波纳切"型，由前往后推。

代码

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
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public int numDecodings(String s) {
        //1:数字要大于等于1，小于等于26
        //2:新加入的数字是否为0
        if(s==null||"".equals(s)||"0".equals(s)||s.charAt(0)=='0'){
            return 0;
        }
        char[] ch=s.toCharArray();
        int[] in= new int[ch.length];
        in[0]=1;
        if(ch.length>=2){
            //计算dp初始值
            int empty=(ch[0]-'0')*10+(ch[1]-'0');
            if(empty>9&&empty<27){
                if(ch[1]=='0'){
                    in[1]=1;
                }else{
                    in[1]=2;
                }
            }else{
                if(ch[1]=='0'){
                    return 0;
                }else{
                    in[1]=1;
                }
            }
            //dp计算出最终值
            for(int i =2;i<in.length;i++){
                int temp = (ch[i-1]-'0')*10+(ch[i]-'0');
                if(temp>9&&temp<27){
                    in[i]+=in[i-2];
                    if(ch[i]!='0'){
                        in[i]+=in[i-1];
                    }
                }else{
                    if(ch[i]!='0'){
                        in[i]+=in[i-1];
                    }else{
                        return 0;//无法解码       
                    }
                }
            }
        }
        return in[in.length-1];
    }
}