639. 解码方法 II

Smile_slime_47
  1999-01-01 1999-01-01 Created    

原题地址：https://leetcode.cn/problems/decode-ways-ii/

题解

设dp[i][0]为第i个字符单独解析的组合数，dp[i][1]为第i个字符和前一个字符组合解析的组合数

本质的思想是根据前一个字符和当前字符的具体情况分类讨论DP

对于第i个字符单独解析的情况

  • 当i为0时，无法单独解析
    • dp[i][0]=0
  • 当i为*时，可以解析为1-9中的任何一个数字，有9种情况
    • 由于i单独解析，因此第i-1个字符无论是单独解析还是与i-2组合解析的情况都可以被算进来
    • dp[i][0]=(dp[i-1][0]+dp[i-1][1])*9
  • 当i为某数字时，i只能被解析为当前数字，只有1种情况
    • dp[i][0]=(dp[i-1][0]+dp[i-1][1])*1

对于第i个字符组合解析的情况

  • 当i-1为1时
    • 当i为*时，可以解析为1-9中的任何一个数字，有9种情况
    • 由于i组合解析，因此i-1也只能取单独解析的情况来和i组合
    • dp[i][0]=dp[i-1][0]*9
    • 当i为某数字时，i只能被解析为当前数字，只有1种情况
    • dp[i][0]=dp[i-1][0]*1
  • 当i-1为2时
    • 当i为*时，i只能被解析为1-6中的任何一个数字，有6种情况
    • dp[i][0]=dp[i-1][0]*6
    • 当i<=6时，i可以被解析为当前数字，有1种情况
    • dp[i][0]=dp[i-1][0]*1
    • 当i>6时，i无法和i-1组合解析
    • dp[i][0]=0
  • 当i-1为*时
    • 当i也为*时，由于无法被解析为0，因此二者只能解析为1119,2126，共15种情况
    • 由于这里是i-1和i作为一个整体计算的，因此应当乘以i-2的组合数
    • dp[i][1]=(dp[i-2][0]+dp[i-2][1])*15;
    • 当i<=6时，i-1可以被解析为1或2，i只能被解析为当前数字，有2种情况
    • dp[i][1]=(dp[i-2][0]+dp[i-2][1])*2;
    • 当i>6时，i-1可以被解析为1，i只能被解析为当前数字，有1种情况
    • dp[i][1]=(dp[i-2][0]+dp[i-2][1])*1;
    • 考虑到边界条件，当i<=1时，dp[i-2][0]+dp[i-2][1]应当等于1

最后记得将结果%=1e7即可

时间复杂度：O(N)

空间复杂度：O(N)

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
class Solution {
    public int numDecodings(String s) {
        long[][] dp=new long[s.length()][2];
        if(s.charAt(0)=='*'){
            dp[0][0]=9;
        }else if(s.charAt(0)=='0'){
            dp[0][0]=0;
        }else{
            dp[0][0]=1;
        }

        for(int i=1;i<s.length();i++){
            if(s.charAt(i)=='*'){
                dp[i][0]=(dp[i-1][0]+dp[i-1][1])*9;
            }else if(s.charAt(i)=='0'){
                dp[i][0]=0;
            }else{
                dp[i][0]=(dp[i-1][0]+dp[i-1][1])*1;
            }

            if(s.charAt(i-1)=='1'){
                if(s.charAt(i)=='*'){
                    dp[i][1]=dp[i-1][0]*9;
                }else{
                    dp[i][1]=dp[i-1][0]*1;
                }
            }else if(s.charAt(i-1)=='2'){
                if(s.charAt(i)=='*'){
                    dp[i][1]=dp[i-1][0]*6;
                }else if(s.charAt(i)<='6'){
                    dp[i][1]=dp[i-1][0]*1;
                }
            }else if(s.charAt(i-1)=='*'){
                if(s.charAt(i)=='*'){
                    dp[i][1]=(i>1?dp[i-2][0]+dp[i-2][1]:1)*15;
                }else if(s.charAt(i)<='6'){
                    dp[i][1]=(i>1?dp[i-2][0]+dp[i-2][1]:1)*2;
                }else{
                    dp[i][1]=(i>1?dp[i-2][0]+dp[i-2][1]:1)*1;
                }
            }

            dp[i][0]%=1000000007;
            dp[i][1]%=1000000007;
        }
        return (int)(dp[s.length()-1][0]+dp[s.length()-1][1])%1000000007;
    }
}
Comments
On this page
639. 解码方法 II
  1. 题解