LeetCode 91 解码方法

段连洁 -

91. 解码方法

Difficulty: 中等

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

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

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

Solution

Language: C++

暴力求解之路

刚开始这道题, 没有太好思路, 但是首先对于算法菜鸟来讲,这类多少种情况的题肯定能用笨方法暴力回溯来解决. 写回溯的呢,就是要明白 ①回溯的截止条件 ② 回溯的当前深度,有哪些选择 ③ 做出选择, 更新参数 递归回溯方法 ④ 恢复之前的选择影响(也就是前一步的副作用) ,做下一种选择.

这里应该不需要将可能的解法保存起来, 只是求数量, 不需要破坏原字符串,也就不需要恢复操作.
解码方法,这里是 数字 转换成 字符. 所以这题的难点是有不少边缘case处理.
首先字符是从 'A' -> 'Z' 对应的数字是从 1 -> 26 , 也就是说我们去解码字符串的时候, 可以选一个, 也可以选2个数字.
如果选择一个, 那么这个字符不能为 '0' ;
如果选择两个, 那么 前后两个字符不能超过 26, 也就是只能是 '1X' -> '2Y', X可以是 0-9 , Y 只能是 0-6.
所以整体需要去做很多 if-else 判断.

​
class Solution
{
public:
    int total;
    int numDecodings(string s)
    {
        if (s.empty() || s[0] == '0')
            return 0;
        // 暴力的方式, 回溯算法 截取一个或者两个
        total = 0;
        numDecodings(s, 0, s.length());
        return total;
    }

    void numDecodings(string &s, int cur, int end)
    {
        if (cur == end)
        {
            total++;
            return;
        }
        // 选择
        if (s[cur] == '0')
        {
            return;
        }
        else if (s[cur] == '1')
        {
            if (cur <= (end - 2))
            { // 可以选两个
                numDecodings(s, cur + 1, end);
                numDecodings(s, cur + 2, end);
            }
            else
            {
                numDecodings(s, cur + 1, end);
            }
        }
        else if (s[cur] == '2')
        {
            if (cur <= (end - 2) && s[cur + 1] <= '6')
            { // 可以选两个
                numDecodings(s, cur + 1, end);
                numDecodings(s, cur + 2, end);
            }
            else
            {
                numDecodings(s, cur + 1, end);
            }
        }
        else
        {
            numDecodings(s, cur + 1, end);
        }
    }
};

上面的暴力解法时间复杂度会很高. O(n^2) 所以提交后 ,会出现超时的.
223 / 258 个通过测试用例 ,卡住的测试用例

"9371597631128776948387197132267188677349946742344217846154932859125134924241649584251978418763151253"

另外分支判断比较杂乱, 其实按照最开始的分析,取两位解码的话可以合并处理

class Solution
{
public:
    int total;
    int numDecodings(string s)
    {
        if (s.empty() || s[0] == '0')
            return 0;
        total = 0;
        numDecodings(s, 0, s.length());
        return total;
    }

    void numDecodings(string &s, int cur, int end)
    {
        // 能走到最后,可能说明解码成功了
        if (cur == end)
        {
            total++;
            return;
        }
        // 无效解码
        if (s[cur] == '0') return;
        //如果可以选两个进行解码
        if (cur <= (end - 2)) {
            if (s[cur] == '1' || 
            (s[cur] == '2' && s[cur + 1] <= '6')) {
                numDecodings(s, cur + 2, end);
            }
        }
        // 绝对可以解码1个的
        numDecodings(s, cur + 1, end);
    }
};

优化后的结果, 可以发现少做了很多判断后提交AC了 , 当然耗时同样很大.

258 / 258 个通过测试用例
状态：通过
执行用时：1016 ms
内存消耗：8.7 MB

合理的递归 与 记忆优化

既然是递归, 那么很容易就会想到优化的方式就是采用 记忆化递归 , 解决递归树中的重复子问题.
例如合法的连续两次解码1位数值 和 一次合法的 解码2位数值, 后面的解码是重复的, 那么我们完全可以采用空间换时间的方式, 存储从该索引到尾部索引这个字符串的解码结果是否成功的标志. 不过尴尬😓的是,我上面的写法完全做不到记录解码结果的样子.
上面的写法是不推荐的,因为这个思路是类似人肉递归的方式, 一直追溯到底部是否解码成功.
推荐的做法是,仅关心当前的解码是否可行, 然后观察后面的解码和当前的解码有什么关系. 让计算机自己递归去解决就可以了.

切忌, 千万不要人肉递归 普通人的脑力完全递归不了几层就出岔子了, 聪明人也不会去那么做 😭 .

同时关于取两位的分支判断: 我们这次从数字的角度看, 只需要查看相邻两位转数字(stoi())后是不是 10 <= number <= 26 即可. 两个字符合并起来的可读性,没这个好理解. 根据上面分析有了下面代码

class Solution
{
public:
     int numDecodings(string s)
    {
        if (s.empty() || s[0] == '0')
            return 0;
        if (s.length() == 1)
            return 1;
        return numDecodings(s, 0, s.length() - 1);
    }

    int numDecodings(string &s, int begin, int end)
    {
        // 无效解码
        if (s[begin] == '0')
            return 0;
        // 仅一位数字 (排除了'0'),有效解码
        if (end - begin <= 0)
            return 1;
        // 起码两位长度的字符串了
        // 先取一位
        int count = numDecodings(s, begin + 1, end);
        const int value = stoi(s.substr(begin, 2));
        // 再取两位
        if (value <= 26)
            count += numDecodings(s, begin + 2, end);
        return count;
    }
};

239 / 258 个通过测试用例 卡在了 
"1787897759966261825913315262377298132516969578441236833255596967132573482281598412163216914566534565"

哈哈 可怜的stoi , 导致超时了

下面是 换成 s[begin] == '1' || (s[begin] == '2' && s[begin+1] <= '6') 字符判断, AC 了 啪啪打脸 😭

class Solution
{
public:
     int numDecodings(string s)
    {
        if (s.empty() || s[0] == '0')
            return 0;
        if (s.length() == 1)
            return 1;
        return numDecodings(s, 0, s.length() - 1);
    }

    int numDecodings(string &s, int begin, int end)
    {
        // 无效解码
        if (s[begin] == '0')
            return 0;
        // 仅一位数字 (排除了'0'),有效解码
        if (end - begin <= 0)
            return 1;
        // 起码两位长度的字符串了
        // 先取一位
        int count = numDecodings(s, begin + 1, end);
        // stoi时间复杂度太高, 导致提交失败ಥ_ಥ
        // 再取两位
        if (s[begin] == '1' 
        || (s[begin] == '2' && s[begin+1] <= '6')) 
            count += numDecodings(s, begin + 2, end);
        return count;
    }
};

258 / 258 个通过测试用例
状态：通过 
执行用时：1160 ms
内存消耗：8.8 MB

递归加上记忆优化吧

class Solution
{
public:
    // 比使用数组效果更好
    unordered_map<int,int> memo;
     int numDecodings(string s)
    {
        if (s.empty())
            return 0;
        return numDecodings(s, 0, s.length() - 1);
    }

    private:
    int numDecodings(const string &s, int begin, int end)
    {
        if (memo.count(begin)) 
            return memo[begin];
        // 无效解码
        if (s[begin] == '0')
            return 0;
        // 仅一位数字 (排除了'0'),有效解码
        if (begin>=end)
            return 1;
        // 起码两位长度的字符串了
        // 先取一位
        int count = numDecodings(s, begin + 1, end);
        // 再取两位 查看花花酱大神的代码实现,发现简单实现 stoi 效率比直接判断字符还高 ಥ_ಥ 
        const int prefix = (s[begin] - '0') * 10 + (s[begin + 1] - '0');
        if (prefix <= 26) 
            count += numDecodings(s, begin + 2, end);
        // 记忆
        memo[begin] = count;
        return count;
    }
};


执行用时 :4 ms, 在所有 C++ 提交中击败了73.17%的用户
内存消耗 :9.9 MB, 在所有 C++ 提交中击败了5.06%的用户

此处的优化是, 使用 (s[begin] - '0') * 10 + (s[begin + 1] - '0') 计算 stoi 比 判断 s[begin] == '1' || (s[begin] == '2' && s[begin+1] <= '6') 快了4ms, 反转又被啪啪打脸 😭
而使用 vector 记录和使用 unordered_map 效率差不多.

动态规划

从上面的代码分析可以看出,这种递归树,往往可以采用自底向上的动态规划处理, 或者经常刷题的小伙伴
可能感觉上面的递归树如果由底向上的话, 这个很类似斐波那契或者爬楼梯的意思.
做动态规划的步骤

  • 找状态定义, 不同的状态定义可能导致不同的时间复杂度;
    • 状态定义要包含 变化的条件
    • 这里定义为: dp[i] 为 索引 0~i的子字符串的解码数量
  • 找状态迁移方程
    • 当前索引 i 的字符串 可以从 i-1的位置解码过来, 或者 i-2的解码位置过来
    • 也就是 dp[i] = dp[i-1] + dp[i-2] 的值

下面题解

class Solution {
public:
     int numDecodings(string s)
    {
        if (s.empty() || s[0] == '0')
            return 0;
        if (s.length() == 1) return 1;
        // 定义 dp[i] 为从0~i的子字符串的解码情况
        vector<int> dp(s.length(),0);
        // 空字符串 解码为一种
        // dp[-1] = 1; 不支持 索引为-1,所以后面要注意dp[i-2]的判断
        // 单个字符的话(排除了'0') 解码为一种
        dp[0] = 1;
        /// 我们仅仅需要累计 解码一个字符与解码两个字符 的情况即可
        for (int i = 1; i< s.length();++i) {
            if (!isValid(s[i]) && !isValid(s[i-1],s[i])) { // 如果s[i] 无效 且 s[i]s[i-1] 那么不管s[i-2]如何大,都没用,后面的两个数值都无法完成解码
                // dp[i] = 0 + 0; // 这里直接就可返回了,很明显当前无解,后面也无解
                return 0;
            } else if (!isValid(s[i]) && isValid(s[i-1],s[i])) { // 如果 s[i] 无效, s[i-1][i] 有效, 说明两个字符的解码成功, 一个字符的解码失败
                dp[i] = 0 + (i == 1 ? 1 : dp[i-2]);
            } else if (isValid(s[i]) && !isValid(s[i-1],s[i])) { // 如果 s[i] 有效 s[i-1]s[i] 无效 ,那么 说明两个字符的没有解码成功, 一个字符的解码成功了 
                dp[i] = dp[i-1] + 0;
            } else { // 肯定是 两个都有效了
                dp[i] = dp[i-1]  + (i == 1 ? 1 : dp[i-2]);
            }
        }
        return dp[s.length() - 1];
    };
   private:
    bool isValid(const char c) { return c != '0'; }
    bool isValid(const char c1, const char c2) { 
        const int num = (c1 - '0')*10 + (c2 - '0');
        return num >= 10 && num <= 26;
    }
};

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :8.6 MB, 在所有 C++ 提交中击败了11.05%的用户

时间复杂度 O(n)
空间复杂度 O(n)

由于状态迁移方程 dp[i] = dp[i-1] + dp[i-2] 可以知道, 当前状态仅仅和前两个状态有关, 所以空间优化可以采用 两个变量, 迭代更新即可.类似 斐波那契方程

class Solution {
public:
     int numDecodings(string s)
    {
        if (s.empty() || s[0] == '0')
            return 0;
        if (s.length() == 1) return 1;
        // 空字符串 解码为一种
        int pre0 = 1; // dp[-1]
        int pre1 = 1; // dp[0]
        for (int i = 1; i< s.length();++i) {
            int temp = 0; // 当前的解码值
            if (!isValid(s[i]) && !isValid(s[i-1],s[i])) {
                return 0;
            } else if (!isValid(s[i]) && isValid(s[i-1],s[i])) {
                temp = pre0;
            } else if (isValid(s[i]) && !isValid(s[i-1],s[i])) { 
                temp = pre1;
            } else {  
                temp = pre0 + pre1;
            }
            // 更新
            pre0 = pre1;
            // 最后的值
            pre1 = temp;
        }
        return pre1;
    };
   private:
    bool isValid(const char c) { return c != '0'; }
    bool isValid(const char c1, const char c2) { 
        const int num = (c1 - '0')*10 + (c2 - '0');
        return num >= 10 && num <= 26;
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了73.17%的用户
内存消耗 :8.5 MB, 在所有 C++ 提交中击败了31.79%的用户

时间复杂度 O(n)
空间复杂度 O(1)

比较记忆化递归的效率会发现比优化后的动态规划还要高效. 哈哈