0091._decode_ways.md

91. Decode Ways

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/decode-ways/description/

内容描述

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

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

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

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

dp[i]代表s[:i]可以有几种解码方式

例：

s=        "1221"
index      0123


dp[0] = 1  [[1]]
dp[1] = 2  [[1,2], [12]]
  
判断 dp[i] 时，它有两种可能的组合方式：
1. 自身解码
    - 如果当前字符不是'0'，那么dp[i]的组合可以为dp[i-1]的所有组合方式后面都加上当前字符
    - 如果当前字符是'0'，那么dp[i]在这种情况下没有符合的组合方式
2. 和它前面的一个字符一起解码
    - 如果10 <= int(s[i-1:i+1]) <= 26, 那么dp[i]的组合可以为dp[i-2]的所有组合方式后面都加上s[i-1:i+1]
    - 如果int(s[i-1:i+1]) < 10 或者 int(s[i-1:i+1]) > 26，那么dp[i]在这种情况下没有符合的组合方式
    
dp[2] = 3  [[1,2,2], [12,2], [1,22]]
dp[3] = 5  [[1,2,2,1], [12,2,2], [1,22,2], [1,2,21], [12,21]]


注意 dp[0] 与 dp[1] 的处理，

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s or len(s) == 0:
            return 0
        if len(s) == 1 and s[0] == '0':
            return 0
        elif len(s) == 1 and s[0] != '0':
            return 1
        
        dp = [0] * len(s)
        dp[0] = 1 if s[0] != '0' else 0
        
        if 10 <= int(s[:2]) <= 26:
            if s[1] == '0':
                dp[1] = 1
            else:
                dp[1] = 2
        else:
            if s[1] == '0':
                dp[1] = 0
            else:
                dp[1] = dp[0]
        for i in range(2, len(s)):
            if s[i] != '0':
                dp[i] += dp[i-1]
            if 10 <= int(s[i-1:i+1]) <= 26:
                dp[i] += dp[i-2]
        return dp[-1]