leetcode-解码方法

点击:题目链接:一条包含字母 A-Z 的消息通过以下映射进行了 编码 :
‘A’ -> 1
‘B’ -> 2

‘Z’ -> 26
要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,”111” 可以将 “1” 中的每个 “1” 映射为 “A” ,从而得到 “AAA” ,或者可以将 “11” 和 “1”(分别为 “K” 和 “A” )映射为 “KA” 。注意,”06” 不能映射为 “F” ,因为 “6” 和 “06” 不同。
给你一个只含数字的 非空 字符串 num ,请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。

思路

通常情况,判断当前可以解码的个数需要知道上一个字母的解码总数。如果该数为0, 我还需要结合上一个数,若不符合条件,我们就需要直接判断该字符串是不满足条件的。

边界情况,f(-1) = 1, f(0) = 1

  • 若为0, 则判断前一个数是否为1和2, 若总数为f(i) = f(i-1),否则字符串不合格

  • 若前一个数为2,则需要需要判断该数是否在1到6,或者前一个数为1,该数无论0到9,若满足条件,则f(i) = f(i-2)+f(i-1)

    • f(i-1) 为分开解码的情况, f(i-2) 为合并后解码的情况

    由于这里只涉及到f(i-1)和f(i-2), 故我们可以用滚动数组进行替代

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
    public:
    int numDecodings(string s) {
    if (s[0] == '0') return 0;

    int pre = 1, cur = 1;
    for (int i = 1; i < s.size(); ++i) {
    int temp = cur;
    if (s[i] == '0') {
    if (s[i - 1] == '1' || s[i - 1] == '2') cur = pre;
    else return 0;
    }
    else if ((s[i - 1] == '1' || (s[i - 1] == '2') && (s[i] > '0' && s[i] < '7')))
    cur = cur+pre;

    pre = temp;

    }
    return cur;
    }
    };

    复杂度

    时间:O(N), 空间:O(1)

作者

Dylan Zhu

发布于

2021-04-17

更新于

2021-04-17

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...