91.解码方法.md

91. 解码方法

url

题目

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

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

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"111" 可以将 "1" 中的每个 "1" 映射为 "A" ，从而得到 "AAA" ，或者可以将 "11" 和 "1"（分别为 "K" 和 "A" ）映射为 "KA" 。注意，"06" 不能映射为 "F" ，因为 "6" 和 "06" 不同。

给你一个只含数字的 非空 字符串 num ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

方法

code

js

let numDecodings = s => {
    if (s === null || s.length === 0)
        return 0;
    let n = s.length;
    let dp = Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = s[0] === '0' ? 0 : 1;
    for (let i = 2; i <= n; i++) {
        let one = parseInt(s.slice(i-1, i));
        if (one !== 0)
            dp[i] += dp[i-1];
        if (s[i-2] === '0')
            continue;
        let two = parseInt(s.slice(i-2, i));
        if (two <= 26)
            dp[i] += dp[i-2];
    }
    return dp[n];
}

go

func numDecodings(s string) int {
	if len(s) == 0 {
		return 0
	}
	n := len(s)
	dp := make([]int, n+1)
	dp[0] = 1
	if s[0] == '0' {
		dp[1] = 0
	} else {
		dp[1] = 1
	}
	for i := 2; i <= n; i++ {
		one, _ := strconv.Atoi(s[i-1:i])
		if one != 0 {
			dp[i] += dp[i-1]
		}
		if s[i-2] == '0' {
			continue
		}
		two, _ := strconv.Atoi(s[i-1:i])
		if two <= 26 {
			dp[i] += dp[i-2]
		}
	}
	return dp[n]
}

java

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 2; i <= n; i++) {
            int one = Integer.valueOf(s.substring(i - 1, i));
            if (one != 0)
                dp[i] += dp[i - 1];
            if (s.charAt(i - 2) == '0') 
                continue;
            int two = Integer.valueOf(s.substring(i - 2, i));
            if (two <= 26)
                dp[i] += dp[i - 2];
        }
        return dp[n];
    }
}