Skip to content

Latest commit

 

History

History
257 lines (204 loc) · 6.78 KB

File metadata and controls

257 lines (204 loc) · 6.78 KB

English Version

题目描述

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

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

解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,"11106" 可以映射为:

  • "AAJF" ,将消息分组为 (1 1 10 6)
  • "KJF" ,将消息分组为 (11 10 6)

注意,消息不能分组为  (1 11 06) ,因为 "06" 不能映射为 "F" ,这是由于 "6""06" 在映射中并不等价。

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

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

 

示例 1:

输入:s = "12"
输出:2
解释:它可以解码为 "AB"(1 2)或者 "L"(12)。

示例 2:

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

示例 3:

输入:s = "0"
输出:0
解释:没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符,因此没有有效的方法对此进行解码,因为所有数字都需要映射。

示例 4:

输入:s = "06"
输出:0
解释:"06" 不能映射到 "F" ,因为字符串含有前导 0("6""06" 在映射中并不等价)。

 

提示:

  • 1 <= s.length <= 100
  • s 只包含数字,并且可能包含前导零。

解法

动态规划法。

假设 dp[i] 表示字符串 s 的前 i 个字符 s[1..i] 的解码方法数。

考虑最后一次解码中使用了 s 中的哪些字符:

  • 第一种情况是我们使用了一个字符,即 s[i] 进行解码,那么只要 s[i]≠0,它就可以被解码成 A∼I 中的某个字母。由于剩余的前 i-1 个字符的解码方法数为 dp[i-1],所以 dp[i] = dp[i-1]
  • 第二种情况是我们使用了两个字符,即 s[i-1]s[i] 进行编码。与第一种情况类似,s[i-1] 不能等于 0,并且 s[i-1]s[i] 组成的整数必须小于等于 26,这样它们就可以被解码成 J∼Z 中的某个字母。由于剩余的前 i-2 个字符的解码方法数为 dp[i-2],所以 dp[i] = dp[i-2]

将上面的两种状态转移方程在对应的条件满足时进行累加,即可得到 dp[i]的值。在动态规划完成后,最终的答案即为 dp[n]

由于 dp[i] 的值仅与 dp[i-1]dp[i-2] 有关,因此可以不定义 dp 数组,可以仅使用三个变量进行状态转移。

Python3

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1
        for i in range(1, n + 1):
            if s[i - 1] != '0':
                dp[i] += dp[i - 1]
            if i > 1 and s[i - 2] != '0' and (int(s[i - 2]) * 10 + int(s[i - 1]) <= 26):
                dp[i] += dp[i - 2]
        return dp[n]

优化空间:

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        a, b, c = 0, 1, 0
        for i in range(1, n + 1):
            c = 0
            if s[i - 1] != '0':
                c += b
            if i > 1 and s[i - 2] != '0' and (int(s[i - 2]) * 10 + int(s[i - 1]) <= 26):
                c += a
            a, b = b, c
        return c

Java

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0') <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

优化空间:

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int a = 0, b = 1, c = 0;
        for (int i = 1; i <= n; ++i) {
            c = 0;
            if (s.charAt(i - 1) != '0') {
                c += b;
            }
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0') <= 26) {
                c += a;
            }
            a = b;
            b = c;
        }
        return c;
    }
}

C++

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }
            if (i > 1 && s[i - 2] != '0') {
                if ((s[i - 2] - '0') * 10 + s[i - 1] - '0' <= 26) {
                    dp[i] += dp[i - 2];
                }
            }
        }
        return dp[n];
    }
};

Go

func numDecodings(s string) int {
	n := len(s)
	dp := make([]int, n+1)
	dp[0] = 1
	for i := 1; i <= n; i++ {
		if s[i-1] != '0' {
			dp[i] += dp[i-1]
		}
		if i > 1 && s[i-2] != '0' {
			if (s[i-2]-'0')*10+(s[i-1]-'0') <= 26 {
				dp[i] += dp[i-2]
			}
		}
	}
	return dp[n]
}

C#

public class Solution {
    public int NumDecodings(string s) {
        if (s.Length == 0) return 0;
        
        var f0 = 1;
        var f1 = 1;
        var f2 = 1;
        for (var i = 0; i < s.Length; ++i)
        {
            f0 = f1;
            f1 = f2;
            f2 = 0;
            var two = i > 0 ? int.Parse(string.Format("{0}{1}", s[i - 1], s[i])) : 0;
            if (two >= 10 && two <= 26)
            {
               f2 += f0;  
            }
            if (s[i] != '0')
            {
                f2 += f1;
            }
        }
        return f2;
    }
}

...