长大后想做什么？做回小孩！

0%

LeetCode——解码方法

发表于 分类于 Valine：
本文字数： 469

NO.91 解码方法 中等

GU3iqS.png

思路一：动态规划

dp[i]的含义：s[i]结尾的字符串有多少解法方法。

初始化：大小s.length+1，包含空串。空串初始化为1，只有一个字符，如果字符是0则无法解码即为0，否则初始化为1。

状态转移：从i==2开始，存在三种情况：

  1. i元素和i-1元素都为0，则无法解码(参数是错误编码的字符串)，即return 0；
  2. i-1元素为0，i无法和i-1进行组合，只能作为个位数字进行解码，即dp[i]=d[i-1]。
  3. i元素为0，只能和i-1元素组合为两位数字，如果这个组合后的两位数字大于26则无法正确解码，即return 0；如果小于等于26，即dp[i]=dp[i-2]。
  4. 如果i元素和i-1元素都不为0，判断i和i-1元素组合后的两位数是否大于26，如果大于26则只能单独作为个位数进行解码，即dp[i]=dp[i-1]；如果小于等于26则既能作为两个个位数进行解码也可以作为一个两位数进行解码，即dp[i]=dp[i-1]+dp[i-2]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int numDecodings(String s) {
    int[] dp=new int[s.length()+1];
    //初始化
    dp[0]=1;
    dp[1]=s.charAt(0)=='0'?0:1;
    //状态转移
    for (int i = 2; i <= s.length(); i++) {
        //记录当前字符和前一个字符组成的一个两位数
        int x = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
        if (s.charAt(i - 1) == '0' && s.charAt(i - 2) == '0') {//1
            return 0;
        } else if (s.charAt(i - 2) == '0') {//2
            dp[i]=dp[i-1];
        } else if (s.charAt(i - 1) == '0') {//3
            if (x>26)return 0;
            dp[i]=dp[i-2];
        } else if (x > 26) {//4
            dp[i]=dp[i-1];
        }else {
            dp[i]=dp[i-1]+dp[i-2];
        }
    }
    return dp[s.length()];
}

时间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github