91. 解码方法 [medium]

https://leetcode-cn.com/problems/decode-ways/

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

通过次数51,412 | 提交次数216,575

First Try

没有按照tag来筛选题目，一开始都想不到这是动态规划的题目，还好用递归解决来第一波，后来用动态规划的memoir解决第二波超时问题。另一个tricky的地方是0出现的位置，一开始完全没有考虑到这点，直到提交错误。

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        - 提交错误1： tmd 发现还得考虑0的问题，比如0不允许，70也不允许。
        - 提交错误2: tmd又超时了，整天在超时的关口
        "9272971672512277354953939427689518239714228293463398742522722274929422229859968434281231132695842184" 耗时1120ms
        - 一开始没有想到缓存的用法，总觉得前面都是不一样的，以为没法用上缓存了，要不是超时真不会去尝试
        """
        
        encoding = {str(i) for i in range(1, 27)}
        cache = ["" for i in range(len(s) + 1)]
        def consume(s):
            """每次只选择1个，或两个"""
            if cache[len(s)] != "":
                return cache[len(s)]

            if len(s) == 0:
                return 1
            # 额外处理0的情况，比如“0”为0, “07”为0, '707' 为0
            # 对于"10"的情况，则在上一个s的时候已经被处理考虑到了，此处不用考虑
            if s[0] == "0":
                return 0
            rv = consume(s[1:]) + (consume(s[2:]) if len(s) >= 2 and s[:2] in encoding else 0)

            cache[len(s)] = rv
            return rv

        return consume(s)
                 

执行用时 :24 ms, 在所有 Python 提交中击败了79.67%的用户
内存消耗 :17.9 MB, 在所有 Python 提交中击败了25.00%的用户

91. 解码方法 [medium]​

First Try​

91. 解码方法 [medium]

First Try