LeetCode091——解码方法

我的LeetCode代码仓：https://github.com/617076674/LeetCode

原题链接：https://leetcode-cn.com/problems/decode-ways/description/

题目描述：

LeetCode091——解码方法

知识点：动态规划

思路：动态规划

注意对字符‘0’的特殊处理。

状态定义：

f(x) -------- 字符串s中[0, x - 1]范围内的子字符串的解码总数

状态转移：

如果字符串s的第一个字符为0，直接返回0。

（1）初值条件：

f(0) = 1。这个值的设定只是迭代计算的需要，并无实际意义。

f(1) = 1。

（2）状态转移方程：

a.如果s.charAt(x - 2)对应的字符小于等于2。

a-1：如果s.charAt(x - 2)对应的字符等于2。

a-1-1：如果s.charAt(x - 1)对应的字符小于等于6。

a-1-1-1：如果s.charAt(x - 1)对应的字符不等于0，则f(x) = f(x - 1) + f(x - 2)。

a-1-1-2：如果s.charAt(x - 1)对应的字符等于0，则f(x) = f(x - 2)。

a-1-2：如果s.charAt(x - 1)对应的字符大于6，则f(x) = f(x - 1)。

a-2：如果s.charAt(x - 2)对应的字符等于1。

a-2-1：如果s.charAt(x - 1)对应的字符不等于0，则f(x) = f(x - 1) + f(x - 2)。

a-2-2：如果s.charAt(x - 1)对应的字符等于0，则f(x) = f(x - 2)。

a-3：如果s.charAt(x - 2)对应的字符等于0。

a-3-1：如果s.charAt(x - 1)对应的字符不等于0，则f(x) = f(x - 1)。

a-3-2：如果s.charAt(x - 1)对应的字符等于0，则f(x) = 0。

b.如果s.charAt(x - 2)对应的字符大于2。

b-1：如果s.charAt(x - 1)对应的字符等于0，则f(x) = 0。

b-2：如果s.charAt(x - 1)对应的字符不等于0，则f(x) = f(x - 1)。

时间复杂度和空间复杂度均是O(n)，其中n为字符串s的长度。

JAVA代码：

class Solution {
    public int numDecodings(String s) {
        int[] counts = new int[s.length() + 1];

        counts[0] = 1;
        if (s.charAt(0) == '0') {
            return 0;
        }
        counts[1] = 1;
        for (int i = 2; i <= s.length(); i++) {
            if (s.charAt(i - 2) - '0' <= 2) {
                if (s.charAt(i - 2) == '2') {
                    if (s.charAt(i - 1) - '0' <= 6) {
                        if (s.charAt(i - 1) != '0') {
                            counts[i] = counts[i - 1] + counts[i - 2];
                        } else {
                            counts[i] = counts[i - 2];
                        }
                    } else {
                        counts[i] = counts[i - 1];
                    }
                } else if (s.charAt(i - 2) == '1') {
                    if (s.charAt(i - 1) != '0') {
                        counts[i] = counts[i - 1] + counts[i - 2];
                    } else {
                        counts[i] = counts[i - 2];
                    }
                } else {
                    if (s.charAt(i - 1) != '0') {
                        counts[i] = counts[i - 1];
                    } else {
                        counts[i] = 0;
                    }
                }
            } else {
                if (s.charAt(i - 1) == '0') {
                    counts[i] = 0;
                } else {
                    counts[i] = counts[i - 1];
                }
            }
        }
        return counts[s.length()];
    }
}

LeetCode解题报告：

LeetCode091——解码方法

LeetCode091——解码方法

思路：动态规划

相关推荐