91-解码方法

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

一条包含字母 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) 。

---

解法

核心思想：利用动态规划的思想，利用前两位来更新当前位置

算法设计如下：

• 特判，若s为空或者s[0]==”0”，返回0

• 初始化dp=[0,…,0]，长度为n+1，dp[0]=1,dp[1]=1。dp[1]=1表示第一位的解码方法，dp[0]的作用，在于两位时，如：”12”，dp[2]=dp[1]+dp[0]。

• 遍历s，遍历区间[1,n)：

  • 若s[i]==”0”：
    • 若s[i-1]=="1" or s[i-1]=="2"：
      • 此时，到当前位置的解码方法dp[i+1]和上上一位的相同，
      • 因为上一位和本位置结合在了一起。dp[i+1]=dp[i-1]
    • 否则，返回0，表示无法解码
  • 否则：
    • 判断何时既可以自身解码也可以和前一位结合：
    • 若上一位s[i-1]==”1”，则当前位既可以单独解码也可以和上一位结合。
    • 或者上一位s[i]==”2”，则此时，若1”<=s[i]<=”6”，也是可以的。
    • 综上，s[i-1]=="1" or (s[i-1]=="2" and "1"<=s[i]<="6")。
    • 此时，dp[i+1]=dp[i]+dp[i-1]，等于上一位和上上位的解码方法之和。
    • 否则，dp[i+1]=dp[i]

• 返回dp[n]

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == "0":
            return 0
        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1
        for i in range(1,n):
            if s[i] == "0":
                if s[i - 1] == "1" or s[i - 1] == "2":
                    dp[i + 1] = dp[i - 1]
                else:
                    return 0
            else:
                if s[i - 1] == "1" or (s[i - 1] == "2" and "1" <= s[i] <= "6"):
                    dp[i + 1] = dp[i] + dp[i - 1]
                else:
                    dp[i + 1] = dp[i]
        return dp[n]

---

相关信息

LeetCode：Discussion | Solution