[C++&Rust]LeetCode No.91 解码方法

原贴地址：

题目

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

A -> 1
B -> 2
...
Z -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：

“AAJF” ，将消息分组为 (1-1-10-6) “KJF” ，将消息分组为 (11-10-6) 注意，消息不能分组为 (1-11-06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

思路分析

dp：动态规划 dfs：深度优先搜索 这个题目是一个分割的题目，常见的做法有dfs和dp。 鉴于dp的性能更好，我们来分析如何使用dp实现这个问题。

动态规划有一个限制，即这个问题能不能被分解成子问题。那我们先假设我们有了子问题的解，也就是对于"11106"来说，我们知道了"1",“11”,“111”,"1110"分别可以有1, 2, 3, 2种方案，那么我们可以靠这些数据推导出"11106"对应的方案数吗？其实对我们来说，需要注意的点就是"0"和"6"两个数字，对于“06”来说，它不能进行组合，所以我们必须将其分割，那么"11106"的分割方案数应该等于"1110"的方案数。 我们对这些情况进行归纳

我们将这个情况对应到dp中，设n为当前处理到的长度 如果可以组合 dp[n] += dp[n - 2] 如何可以分割 dp[n] += dp[n - 1] 起始条件是0，边缘条件是dp[-1]是1 那么如何判断组合和分割的情况呢？ 我们可以通过观察上表的最后两位举例，来试试推导出按照最后两位判断是否可以判断和分割的情况，我们可以看出，后两位大于等于"10"且小于等于"26"的时候是可以组合的。 最后一位不等于0的时候是可以分割的，我们的代码当然也是基于这个想法。 C++代码

class Solution {
          
   
public:
    int numDecodings(string s) {
          
   
        vector<int> res = {
          
   1, 1};
        int reslen = 2;
        char pre = 0;
        for (auto & ch : s) {
          
   
            int tmp = 0;
            if (pre == 1 || (pre == 2 && ch <= 6)) tmp += res[reslen - 2];
            if (ch != 0) tmp += res[reslen - 1];
            res.push_back(tmp);
            reslen++;
            pre = ch;
        }
        return res.back();
    }
};

Rust代码

impl Solution {
    pub fn num_decodings(s: String) -> i32 {
        let mut res = vec![1, 1];
        let mut reslen = 2;
        let mut pre = 0;
        for ch in s.chars() {
            let mut tmp = 0;
            if (pre == 1 || (pre == 2 && ch <= 6)) {
                tmp += res[reslen - 2];
            }
            if (ch != 0) {
                tmp += res[reslen - 1];
            }
            res.push(tmp);
            reslen += 1;
            pre = ch;
        }
        res[reslen - 1]
    }
}

最近可能会出第22期CCF-CSP的题解，上次考崩了，只有320，希望能通过题解更好的提升自己的业务水平！