tags: Leetcode medium dynamic programming python

91. Decode Ways

[題目連結:] https://leetcode.com/problems/decode-ways/

題目:

A message containing letters from A-Z can be encoded into numbers using the following 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 ways). For example, "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)
• "KJF" with 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 ways to decode it.

The test cases are generated so that the answer fits 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).

Example 3:

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").

解題想法:

• 題目為，給一數字，求其可以表示的解碼組合數
• 使用DP:
  • 定義dp[i]: 前i個數字字元的組合總數，dp[len(s)]即為所求
    • init: dp[0]=1 沒有數字，一種組合
  • dp[i]=dp[i-1]+dp[i-2]
    • 相當於上階梯，可以每次上一階or兩階
  • case1: 當前數字自己視為一個字母(自己不能為'0')->總組合數與dp[i-1]一樣
  • case2: (當前數字自己+前一個數子)視為一個字母->總組合數與dp[i-2]一樣
    • 額外注意，因為以0為起始不可構成任何字串，所以要確認前一個數字是否為0

ex: s='226'
22: 可以decode為 2，2->BB or 22->V 
在考慮6時:
case1: 可以6自己視為字符，所以總數繼承dp[i-1]
case2: 可以與前面一數進行組合，
因為 s[i-2](2)!=0 且 s[i-2]+s[i-1]<=26
所以26可以編碼為Z
所以可以繼承dp[i-2]
所以最終dp[i]=dp[i-1]+dp[i-2]=3

Python:

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        #dp[i]:前i個字元的組合總數
        n = len(s)
        dp = [0]*(n+1)
        dp[0]=1
        for i in range(1,len(dp)):
            if s[i-1]!='0':
                dp[i]+=dp[i-1]
            if i>1 and s[i-2]!='0' and int(s[i-2]+s[i-1])<=26:
                dp[i]+=dp[i-2]
        return dp[n]

result = Solution()
ans = result.numDecodings("226")
print(ans)