Leetcode 91. Decode Ways (python+cpp)

题目

解法1：recursion + memorization

这种方法是leetcode官方提供的一种，说实话我觉着理解起来不是那么直观，所以这边不多做解释
python代码如下：

class Solution:def numDecodings(self, s: str) -> int:# recursion with memorizationdef dfs(index):if index == len(s):return 1if s[index] == '0':return 0if index in memo:return memo[index]if index < len(s)-1:ans = dfs(index+1) + (dfs(index+2) if (int(s[index:index+2]) <= 26) else 0)else:ans = dfs(index+1)memo[index] = ansreturn ansif not s:return 0memo = {
    }return dfs(0)

解法2：动态规划

这道题目如果仔细考虑，会发现其实是70 climbing stairs的变形。因为由于题目的设定，数字分割成的子部分只可能是长度1或者2，这就对应爬楼梯里的爬1步或者爬2步，只不过这边爬1步或者爬2步是有条件的。这边的状态转移方程应该是：

dp[i] = dp[i-1] if condition1 satisfy+ dp[i-2] if condition2 satisfy

condition1代表当前位置的字符不能是0，而condition2代表当前的两个子字符串必须在9~27之间。

这边与爬楼梯还有一点不同是dp的初始化，对于爬楼梯：

dp = [0]*(n+1)
dp[0] = dp[1] = 1

或者

dp = [1]*(n+1)

都是可以的。但是这道题不一样，这道题由于每一步或者两步有条件限制，所以dp的default值必须为0，并需要将dp[0]手动设1，具体细节可以仔细考虑考虑。
python代码如下：

class Solution:def numDecodings(self, s: str) -> int:# 1-D dpdp = [0] * (len(s) + 1)dp[0] = 1for i in range(1, len(dp)):if s[i-1] != '0':dp[i] = dp[i-1]if i != 1 and '09' < s[i-2:i] < '27':dp[i] += dp[i-2]return dp[-1]

由于dp[i]只与dp[i-1]和dp[i-2]相关，所以也可以进行状态压缩，状态压缩后的python代码如下：

class Solution:def numDecodings(self, s: str) -> int:# constant space dpw, v, p = 0, 1, 0for i in range(1, len(s) + 1):if s[i-1] != '0':w = vif i != 1 and '09' < s[i-2:i] < '27':w += pw, v, p = 0, w, v return v

C++版本一维dp代码如下：

class Solution {
    
public:int numDecodings(string s) {
    vector<int> dp(s.size()+1);dp[0] = 1;for (int i=1;i<dp.size();i++){
    if (s[i-1] != '0') dp[i] = dp[i-1];if (i!=1 && s.substr(i-2,2)>"09" && s.substr(i-2,2)<"27") dp[i] = dp[i]+dp[i-2];}return dp.back();}
};

参考链接：https://leetcode.com/problems/decode-ways/discuss/163707/Python-From-O(N)-Space-To-O(1)-Space-Solutions