Decode Ways

发表于 | 分类于

Decode Ways

题目描述：

给定一个数字字符串和各个数字字符串对应的字母字符，要求找到这个数字字符可以被解码为字母串的可能数。

例子：

具体描述见LeetCode91

解题思路：

首先我们遍历字符串中的每个字符的时候，我们需要判断当前的字符是不是0，因为如果是0的情况下，可能出现不符合要求的字符串，比如123406；如果是合理的0字符，则当前字符的可能组合数和上一个字符是一致的；如果是不合理的字符0直接返回0；其次在当前字符不是0的情况下，我们判断两种情况；一种是能否和上一个字符组合，可以的情况下就是当前字符的可能和上一个字符可能数相加；如果无法组合就是当前字符的组合了(本题中主要用到的是DP的想法，需要注意的是0字符的处理)

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int numDecodings(string s) {
        if (s == "" || s[0] == '0') return 0;
        vector<int> res(2, 1);
        
        for (int i = 1; i < s.size(); i++){
            int temp = (s[i] - '0') + 10 * (s[i - 1] - '0');
            if (s[i] == '0'){
                if (temp > 20 || temp == 0) return 0;
                else res.push_back(res[i - 1]);
            }else{
                if (temp >= 27 || temp < 10){
                    res.push_back(res[i]);
                }else{
                    res.push_back(res[i] + res[i - 1]);
                }
            }
        }
        return res[res.size() - 1];
    }
};