91. Decode Ways

现在有如下的字母与数字的对应关系：1-A, 2-B, …26-Z。给定一个由数字组成的字符串，判断按照上面的映射可以转换成多少种不同的字符串

思路： 动态规划，分类讨论, dp[i]表示前i个字符的最多解码方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        # dp, 6 star, 还没理解，需重看, 几个情况的分类讨论需要注意
        if s == "" or s[0] == "0":
            return 0
        n = len(s)
        dp = [0] * (n+1)
        dp[:2] = [1, 1]
        for i in range(2, n+1):
            before = int(s[i-2:i])
            if 26 >= before > 10 and before != 20: # 大于10小于26且不等于20的，有两种情况，一种是dp[i-1] 一种是dp[i-2]
                dp[i] = dp[i-1] + dp[i-2]
            elif before in (10, 20): # 10 和 20 只能有一种解码方式，所以等于 dp[i-2]
                dp[i] = dp[i-2]
            elif 9 >= int(s[i-1]) >= 1: #  这种是大于26且各位上不是0的 等于 dp[i-1]
                dp[i] = dp[i-1]
            # 剩余的就是大于26且个位是0的了，例如 40 50，这种根本无法解码，所以dp[i]=0
        return dp[-1]

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func numDecodings(s string) int {
	if s == "" || string(s[0]) == "0" {return 0}
	length := len(s)
	dp := make([]int, length+1)
	dp[0], dp[1] = 1, 1
	for i:=2; i < length + 1; i++{
		cur, _ := strconv.Atoi(s[i-2:i])
		if cur <= 26 && cur > 10 && cur != 20 {
			dp[i] = dp[i-1] + dp[i-2]
		} else if cur == 10 || cur == 20 {
			dp[i] = dp[i-2]
		} else {
			if before, _ := strconv.Atoi(string(s[i-1])); before != 0 {  // 排除cur是70 80这一类情况
				dp[i] = dp[i-1]
			}

		}
	}
	return dp[length]

}