[剑指 Offer 第 2 版第 46 题] “把数字翻译成字符串”做题记录

第 46 题：把数字翻译成字符串

传送门：把数字翻译成字符串。

给定一个数字，我们按照如下规则把它翻译为字符串：

0 翻译成 “a”，1 翻译成 “b”，……，11 翻译成“l”，……，25 翻译成 “z”。

一个数字可能有多个翻译。例如 12258 有 5 种不同的翻译，它们分别是 “bccfi”、“bwfi”、“bczi”、“mcfi” 和 “mzi”。

请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

样例：

输入："12258"

输出：5

思路：同 LeetCode 第 91 题 Decode Ways。使用动态规划。状态：dp[i] 表示 s[0,i] （包括 i ），一共有多少种翻译的方法。分类讨论：1、当前字符可以单独翻译；2、当前字符可以和前面一个字符一起翻译。dp[i] 就是以上二者之和。

Python 代码：

  class Solution:
        def getTranslationCount(self, s):
            """
            :type s: str
            :rtype: int
            """
            s = str(s)
            l = len(s)
            if l == 0:
                return 0
            dp = [None for _ in range(l)]

            # dp[i] 表示 s[0,i] ，包括 i ，一共有多少种翻译的方法

            dp[0] = 1
            for i in range(1, l):
                # 当前值至少是 dp[i-1]，因为 s[i] 一定可以单独翻译
                cur = dp[i - 1]

                # 看一看 s[i-1,i] 是不是可以翻译
                if 9 < int(s[i - 1:i + 1]) < 26:
                    if i - 2 < 0:
                        # 12
                        cur += 1
                    else:
                        # 要考虑到数组下标越界问题
                        cur += dp[i - 2]
                dp[i] = cur
            return dp[l - 1]

LeetCode 第 91 题：解码方法

传送门：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) 。

Python 代码：

  # 91、解码方法
    # 一条包含字母 A-Z 的消息通过以下方式进行了编码：
    #
    # 'A' -> 1
    # 'B' -> 2
    # ...
    # 'Z' -> 26
    # 给定一个只包含数字的非空字符串，请计算解码方法的总数。


    class Solution:

        def numDecodings(self, s):
            """
            :type s: str
            :rtype: int
            """

            l = len(s)
            if l == 0:
                return 0

            if l == 1:
                return 1 if s[0] != '0' else 0
            dp = [0 for _ in range(l)]
            dp[0] = 1 if s[0] != '0' else 0
            for i in range(1, l):
                if s[i] != '0':
                    # 如果不是 '0' ，那么 s[i] 就可以编码，所以 cur 就至少是  dp[i-1]
                    dp[i] += dp[i - 1]
                if 9 < int(s[i - 1:i + 1]) < 27:
                    # 可以和前面的数字组成一个编码
                    if i - 2 < 0:
                        # 12
                        dp[i] += 1
                    else:
                        dp[i] += dp[i - 2]
            return dp[l - 1]


    if __name__ == '__main__':
        test_str = '12'
        s = Solution()
        res = s.numDecodings(test_str)
        print(res)

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/