力扣 91. 解码方法

题目说明

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

    1
    2
    3
    4
    '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.length <= 100
    • s 只包含数字，并且可能包含前导零。

示例

例1

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

例2

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

例3

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

例4

1
2
3
输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。

笔者理解

此题是一道字符串算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题就像是带约束条件版的青蛙跳台阶问题，也就是动态规划问题，在本题中只需要搞清楚字符串相邻字符的组合可能情况就好了，让我们来看看具体如何实现的吧。

实现

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 int numDecodings(String s) {
        // 首字符为0为不合法
        if (s.charAt(0) == '0') {
            return 0;
        }
        int size = s.length();

        int[] dp = new int[size + 1];
        dp[0] = 1;
        dp[1] = 1;

        /*
        例如 s = "1101127"
        dp[0] = 1  dp[1] = 1
        i = 1  dp[2] = 2                    11  : K
                                            1,1 : A,A 

        i = 2  dp[2] = 0  dp[3] = 1         1,10   : A,J

        i = 3  dp[4] = 1                    1,10,1 : A,J,A

        i = 4  dp[5] = dp[4] + dp[3] = 2    1,10,11  : A,J,K  
                                            1,10,1,1 : A,J,A,A

        i = 5  dp[6] = dp[5] + dp[4] = 3    1,10,11,2  : A,J,K,B 
                                            1,10,1,12  : A,J,A,A,L  
                                            1,10,1,1,2 : A,J,A,A,B 

        i = 6  dp[7] = dp[6]                1,10,11,2,7  : A,J,K,B,G  
                                            1,10,1,12,7  : A,J,A,A,L,G  
                                            1,10,1,1,2,7 : A,J,A,A,B,G
        */

        for (int i = 1; i < size; i++) {
            // 当前字符为0，则它不可以单独组成字母，i位置的组成可能为0
            if(s.charAt(i) == '0') {
                dp[i] = 0;
            }
            // 若当前字符能和上一个字符组成字母，则i + 1位置组成可能等于i和i - 1位置的组合可能的和
            if(s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) - '0' <= 6)) {
                dp[i + 1] = dp[i] + dp[i - 1];
            }
            // 若当前字符不能和上一个字符组成字母，则i + 1位置组成可能等于i的组合可能
            else{
                dp[i + 1] = dp[i];
            }
        }

        return dp[size];
    }

时间和空间效率都还行，可见此解法还比较适合此题；

image.png

总结

本题是今天的每日一题，难度是为中等，感兴趣的朋友都可以去尝试一下，此题还有其他更多的解法，朋友们可以自己逐一尝试。