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).

Solutions

  给一串数字,找出其能表示的最多字母组合。

1. DP

  看例子 226 其实可以拆分成两个部分来看待,取一个字符,看其是否符合要求,如果符合就把其到这个一个字符位置的组合个数算上,如果不符合那就不算,留着零的状态;然后取两个字符采用同样的过程。

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0

        dp = [0 for x in range(len(s) + 1)] 

        # base case initialization
        dp[0] = 1 
        dp[1] = 0 if s[0] == "0" else 1   #(1)

        for i in range(2, len(s) + 1): 
            # One step jump
            if 0 < int(s[i-1:i]) <= 9:    #(2)
                dp[i] += dp[i - 1]
            # Two step jump
            if 10 <= int(s[i-2:i]) <= 26: #(3)
                dp[i] += dp[i - 2]
        return dp[len(s)]

# Runtime: 24 ms, faster than 44.72% of Python online submissions for Decode Ways.
# Memory Usage: 11.8 MB, less than 65.22% of Python online submissions for Decode Ways.

References

  1. 91. Decode Ways
  2. Java clean DP solution with explanation