218 - 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) 。

解答

每个数字一个数，两两组合一个数，组合还要看不要超过26

https://leetcode-cn.com/problems/decode-ways/solution/dong-tai-gui-hua-tu-jie-by-nfgc/

class Solution:
    def numDecodings(self, s: str) -> int:
        pp, p = 1, int(s[0] != "0")
        for i in range(1, len(s)):
            pp, p = p, pp*(9 < int(s[i-1:i+1]) <= 26)+p*(int(s[i]) > 0)
        return p

Runtime: 28 ms, faster than 83.56% of Python3 online submissions for Decode Ways.

Memory Usage: 12.5 MB, less than 100.00% of Python3 online submissions for Decode Ways.

https://leetcode.com/problems/decode-ways/discuss/30379/1-liner-O(1)-space

class Solution:
    def numDecodings(self, s: str) -> int:
        v, w, p = 0, int(s > ""), ""
        for d in s:
            v, w, p = w, (d > "0")*w+(9 < int(p+d) < 27)*v, d
        return w

Runtime: 28 ms, faster than 83.56% of Python3 online submissions for Decode Ways.

Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for Decode Ways.

递归

https://leetcode-cn.com/problems/decode-ways/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-2-3/

class Solution:
    def numDecodings(self, s: str) -> int:
        def recu(i):
            if i == len(s):
                return 1
            if s[i] == '0':
                return 0
            ans1 = recu(i+1)
            ans2 = 0
            if i < len(s)-1:
                if int(s[i]+s[i+1]) <= 26:
                    ans2 = recu(i+2)
            return ans1+ans2

        return recu(0)

超时了

带备忘录的递归

class Solution:
    def numDecodings(self, s: str) -> int:
        memo = {}

        def recu(i):
            if i == len(s):
                return 1
            if s[i] == '0':
                return 0
            if i in memo:
                return memo[i]
            ans1 = recu(i+1)
            ans2 = 0
            if i < len(s)-1:
                if int(s[i]+s[i+1]) <= 26:
                    ans2 = recu(i+2)
            memo[i] = ans1 + ans2
            return ans1+ans2

        return recu(0)

Runtime: 36 ms, faster than 27.57% of Python3 online submissions for Decode Ways.

Memory Usage: 13.7 MB, less than 16.00% of Python3 online submissions for Decode Ways.

自底向上

https://leetcode.com/problems/decode-ways/discuss/30358/Java-clean-DP-solution-with-explanation

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s:
            return 0
        n = len(s)
        dp = [0]*(n+1)
        dp[0] = 1
        dp[1] = 1 if s[0] != '0' else 0
        for i in range(2, n+1):
            first = int(s[i-1:i])
            second = int(s[i-2:i])
            if first >= 1 and first <= 9:
                dp[i] += dp[i-1]
            if second >= 10 and second <= 26:
                dp[i] += dp[i-2]
        return dp[n]

Runtime: 32 ms, faster than 59.69% of Python3 online submissions for Decode Ways.

Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for Decode Ways.