91.md

题目地址

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

解答1

class Solution:
    total = 0

    def numDecodings(self, s: str) -> int:
        """
            解码方法(算法理解）

            一条包含字母 A-Z 的消息通过以下方式进行了编码：
            'A' -> 1
            'B' -> 2
            ...
            'Z' -> 26
            给定一个只包含数字的非空字符串，请计算解码方法的总数。
            输入: "226"
            输出: 3
            解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
        """
        dict1 = {str(i): chr(ord("A") + i - 1) for i in range(1, 27)}
        res = []
        if not s:
            return 0
        self.dfs(s, res, [], dict1)
        return self.total

    def dfs(self, s, res, buff, dict1):
        if not s:
            return
        if s in dict1.keys():
            buff.append(s)
            res.append(list(buff))
            buff.pop()
            self.total += 1
        for i in range(1, min(len("26") + 1, len(s))):
            if int(s[:i]) > 26:
                return
            elif s[:i] in dict1.keys() and s[:i] in s:
                buff.append(s[:i])
                self.dfs(s[i:], res, buff, dict1)
                buff.pop()
            else:
                return

解答2

class Solution:
    def numDecodings(self, s: str) -> int:
        """
            解码方法(非最优解）

            一条包含字母 A-Z 的消息通过以下方式进行了编码：
            'A' -> 1
            'B' -> 2
            ...
            'Z' -> 26
            给定一个只包含数字的非空字符串，请计算解码方法的总数。
            输入: "226"
            输出: 3
            解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
        """
        if not s:
            return 0
        dp = [0] * (len(s) + 1)  # dp[i]表示以s[0...i)的最多解码方式
        dp[0] = 1
        for i in range(1, len(s) + 1):
            if int(s[i - 1]) != 0:
                if i == 1:
                    dp[i] = 1
                else:
                    if int(s[i - 2]) and int(s[i - 2:i]) <= 26:
                        dp[i] = dp[i - 2] + dp[i - 1]
                    else:
                        dp[i] = dp[i - 1]
            else:
                if i > 1 and 0 < int(s[i - 2:i]) <= 26:
                    dp[i] = dp[i - 2]
                else:
                    return 0

        return dp[len(s)]

解答3

class Solution:
    def numDecodings(self, s: str) -> int:
        """
            解码方法(非最优解)

            一条包含字母 A-Z 的消息通过以下方式进行了编码：
            'A' -> 1
            'B' -> 2
            ...
            'Z' -> 26
            给定一个只包含数字的非空字符串，请计算解码方法的总数。
            输入: "226"
            输出: 3
            解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
        """
        res = [1] + [0] * len(s)
        if not s:
            return 0
        for i in range(0, len(s)):
            if i == 0:
                if s[i] == "0":
                    return 0
                else:
                    res[i + 1] += res[i]
            elif s[i - 1] != "0" and s[i] != "0":
                if 0 < int(s[i - 1:i + 1]) < 27:
                    res[i + 1] += res[i] + res[i - 1]
                else:
                    res[i + 1] += res[i]
            elif s[i - 1] == "0" and s[i] == "0":
                return 0
            elif s[i - 1] == "0":
                res[i + 1] += res[i]
            elif s[i] == "0" and 0 < int(s[i - 1:i + 1]) < 27:
                res[i + 1] += res[i - 1]

        return res[-1]

解答4

class Solution:
    def numDecodings(self, s: str) -> int:
        """
            解码方法

            一条包含字母 A-Z 的消息通过以下方式进行了编码：
            'A' -> 1
            'B' -> 2
            ...
            'Z' -> 26
            给定一个只包含数字的非空字符串，请计算解码方法的总数。
            输入: "226"
            输出: 3
            解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
        """
        count, store = 0, {}

        def helper(s):
            nonlocal count
            if not s:
                count += 1
            elif s[0] == "0":
                pass
            elif s in store:
                count += store[s]
            else:
                helper(s[1:])
                if len(s) >= 2 and int(s[:2]) < 27: helper(s[2:])
                store[s] = count

        helper(s)
        return count