leetcode-decode-ways

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/decode-ways/

　　给你一个字符串，里边只含有数字0-9，而且0对应A，1对应B……26对应Z，问你这个字符串共有多少种解码方式，注意给的输入字符串有可能解码方案数为0，比如“90112”和“1212230”，输出就为0

题目分析

　　思路参考了这里。
https://github.com/haoel/leetcode/blob/master/algorithms/cpp/decodeWays/decodeWays.cpp

　　利用动态规划的思想，转移方程比较简单：

1
2
3
4
5
6
if(check(s.charAt(i)) == 1) {
    dp[i] = dp[i - 1];
}
if(check(s.charAt(i - 1), s.charAt(i)) == 1) {
	dp[i] += dp[i - 2];
}

　　由于dp[i]和dp[i-1],dp[i-2]有关，所以初始化时需要计算出dp[0]和dp[1]。计算dp[1]逻辑稍有点多，主要是因为需要考虑字符串前两位的各种情况，第一个位置分4种情况，0，1，2，3-9，第二个位置分五种情况，0，1，2，3-6，7-9。所以说计算dp[1]的if，else要把这4*5=20种情况都能覆盖到。

　　还要理解一点，dp数组并不是单调不减的，比如“120”。

代码

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
47
48
49
50
public class Solution {
	public int check(char ch) {
		return (ch != '0') == true ? 1: 0;
	}
	
	public int check(char ch1, char ch2) {
		return (ch1 == '1' || (ch1 == '2' && ch2 <= '6')) == true ? 1: 0; 
	}
    public int numDecodings(String s) {
        if(s == null || s.length() == 0) {
            return 0;
        }
        if(s.length() == 1) {
        	return check(s.charAt(0));
        }
        //len >= 2
        int len = s.length();
        int[] dp = new int[len + 1];
        
        dp[0] = check(s.charAt(0));
        if(dp[0] == 0) {
        	dp[1] = 0;
        } else {
        	if(s.charAt(1) == '0') {
        		if (check(s.charAt(0), s.charAt(1)) == 1) {
        			dp[1] = 1;
        		} else {
        			dp[1] = 0;
        		}
        	} else {
        		if (check(s.charAt(0), s.charAt(1)) == 1) {
        			dp[1] = 2;
        		} else {
        			dp[1] = 1;
        		}
        	}
        }
        for(int i = 2; i < len; i++) {
        	if(check(s.charAt(i)) == 1) {
        		dp[i] = dp[i - 1];
        	}
        	if(check(s.charAt(i - 1), s.charAt(i)) == 1) {
        		dp[i] += dp[i - 2];
        	}
        }
        return dp[len - 1];
    }
}

　　时间复杂度O(len)