91-解码方法

LeetCode

发布日期: 2021-10-07

LeetCode 91. Decode resays

A message containing letters from A-Z can be encoded into numbers using the folloresing mapping:

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

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple resays). For example, “11106” can be mapped into:

"AAJF" resith the grouping (1 1 10 6)
"KJF" resith the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of resays to decode it.

The ansreser is guaranteed to fit in a 32-bit integer.

Example 1:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

method 1: 记忆化搜索

一个字符串的解码方法=去除第一个字符的解码方法+去除前两个字符

记忆化方法，哈希表存储每个下标对应的解码数，重复处理下标时可以立即返回

index == n - 1的情况是访问到了最后一个元素
index > n - 1是因为index+2之后越界了，也要直接返回

unordered_map<int, int> hash;
int reversal(string& s, int index) {
    if (hash[index]) return hash[index];
    if (s[index] == '0') return 0;  // 首字母为0，不合法
    if (index >= s.size() -1) return 1; // 到最后一个字母，递归结束
    int res = reversal(s, index + 1);    // 一个字符的情况
    int num = (s[index] - '0') * 10 + (s[index + 1] - '0');
    if (num >= 10 && num <= 26)
        res += reversal(s, index + 2);   // 两个字符的情况
    hash[index] = res;
    return res;
}
int numDecodings(string s) {
    return reversal(s, 0);
}

method 2: 动态规划

0只能和前一个数搭配，如果搭出来是无效的，就直接返回0

基本模型是dp[i] = dp[i-1] + dp[i-2]
不过要加一些条件，如果s[i]有效，就是dp[i] += dp[i-1]
如果s[i-1]s[i]也有效，再加上dp[i-2]

dp[1]要特殊处理一下，不然会越界取到dp[-1]

bool isValue(char c) {
    if (c != '0') return true;
    return false;
}
bool isValue(char c1, char c2) {
    int num = (c1 - '0') * 10 + (c2 - '0');
    if (num >= 10 && num <= 26) return true;
    return false;
}
int numDecodings(string s) {
    int n = s.size();
    if (s[0] == '0') return 0;
    if (n == 1) return 1;
    vector<int> dp(s.size());
    dp[0] = 1;  // 已经确保有两个元素，且s[0]有效，还要考虑dp[1]
    if (!isValue(s[1]) && !isValue(s[0], s[1])) return 0;   // 30 40之类无效的
    if (isValue(s[1])) dp[1] += 1;
    if (isValue(s[0], s[1])) dp[1] += 1;
    for (int i = 2; i < s.size(); i++) {
        if (!isValue(s[i]) && !isValue(s[i - 1], s[i])) return 0;
        if (isValue(s[i])) dp[i] += dp[i - 1];
        if (isValue(s[i - 1], s[i])) dp[i] += dp[i - 2];
    }
    return dp[n - 1];
}

用变量替换数组，就不用考虑越界的问题了

int numDecodings(string s) {
    int n = s.size();
    if (s[0] == '0') return 0;
    if (n == 1) return 1;
    int dp0 = 1;     // 相当于dp[i-2]
    int dp1 = 1;     // 相当于dp[i-1]
    for (int i = 1; i < n; i++) {
        int res = 0;  // 相当于dp[i]
        if (!isValue(s[i]) && !isValue(s[i - 1], s[i])) return 0;
        if (isValue(s[i])) res += dp1;
        if (isValue(s[i - 1], s[i])) res += dp0;
        dp0 = dp1;
        dp1 = res;
    }
    return dp1;
}