LeetCode #91: 解码问题

动态规划教做人


目录

题目

有一种将字母编码成数字的方式: ‘a’ -> 1, ‘b’ -> 2, … , ‘z’ -> 26.

现在给一串数字,给出有多少种可能的译码结果。

读题

一位数的时候, 只有一种解码; 两位数时, 如果数字在 1 到 26 之间, 就可以有两种解码. 要特别注意一下 0, 它本身是没有解码的, 只有 10 和 20 可以解码, 也就是说 100, 30 这种输入是没有解码结果的.

求解

首先是输入是否合法, 对于无输入或者 0, 直接返回 0.

之后从前向后扫描, 对于非 0 元素, 会有两种情况: 它与前面的数字在 1 到 26 之间, 或者不在. 如果不在, 那么它对于解码方法的增加没有贡献, 也是就和它前面的字符串的解码方式相等; 如果在 1 到 26 之间, 就会有把它当成1位数解码和当成2位数解码两种方式, 那么整个字符串的解码方式加 1.

如果扫描到 0, 那么不但它对解码方式增加没有贡献, 还会限制它前面的一个字符: 组合成 10 或 20 时, 0 前面的字符就不能和更前面的字符组合成两位数, 这时解码方式等于前n-2个字符的解码方式; 而如果不能组合成 10 或者 20, 就没办法进行解码, 解码方式为 0.

C++ 代码

 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
int solution(string str) {
    // 排除空输入或者 0 开头的数字
    if (str.size() == 0 || str.front() != '0') {
        return 0;
    }
    // dp[i] 表示到第 i 个字符为止所有解码方式
    vector<int> dp(str.size(), 0);
    // 上面判断了第一个字符不是 0, 所以有一种解码
    dp[0] = 1;
    // 从前向后遍历
    for (int i = 1; i < str.size(); ++i) {
        // 如果当前位不是 0, 那么至少和之前的解码数目相同
        if (str[i] != '0') {
            dp[i] = dp[i - 1];
        }
        // 如果可以和前面组合成可解码数字, 解码方式增加
        if (dp[i - 1] == '1' || (dp[i - 1] == '2' && dp[i] < '6')) {
            if (i - 2 < 0) {
                // 正好是最前面的两个数字, 直接加 1
                ++dp[i];
            } else {
                // 否则再加上前 i - 2 位解码方式
                dp[i] += dp[i - 2];
            }
        }
    }
    // dp 中最后一个元素就是到到最后一个字符为止的解码方式
    return dp.back();
}

看到 dp 数组只用到了两个元素, 空间占用上可以再优化, 不过那样就更看不懂了, 不写了.


emmmm, 上次更新服务器系统时忘了备份数据库, 再加上评论比较少, 暂时关闭评论功能