LeetCode91-解码方法

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/decode-ways/

中文链接：https://leetcode-cn.com/problems/decode-ways/

题目详述

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

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

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

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

示例 2:

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

题目详解

动态规划。注意判断边界条件。

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
public class LeetCode_00091 {

    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') {
            return 0;
        }
        int pre2 = 1;
        int pre1 = 1;
        int res = 1;
        char prec = s.charAt(0);
        for (int i = 1; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == '0') {
                // 当 '0' 出现时，前面一个字符必须为 '1' 或 '2'，否则不是合法序列
                if ((prec == '1' || prec == '2')) {
                    res = pre2;
                } else {
                    return 0;
                }
            } else {
                res = pre1;
                if (prec == '1' || (prec == '2' && c <= '6')) {
                    res += pre2;
                }
            }
            pre2 = pre1;
            pre1 = res;
            prec = c;
        }
        return res;
    }
}