LeetCode-LCR 165 解密数字

题目描述

现有一串神秘的密文 ciphertext，经调查，密文的特点和规则如下：

• 密文由非负整数组成
• 数字 0-25 分别对应字母 a-z

请根据上述规则将密文 ciphertext 解密为字母，并返回共有多少种解密结果。

示例 1：

输入：ciphertext = 216612
输出：6
解释：216612 解密后有 6 种不同的形式，分别是 "cbggbc"，"vggbc"，"vggm"，"cbggm"，"cqgbc" 和 "cqgm" 

提示：

• 0 <= ciphertext < 231

题解

解法一-字符串动态规划

dp[i]表示前i个字符的解密结果数目

字符数字只能为1位(0-9)或者两位(10-25)

class Solution:
    def crackNumber(self, ciphertext: int) -> int:
        ciphertext = str(ciphertext)
        n = len(ciphertext)
        dp = [0] * n
        dp[0] = 1
        for i in range(1, n):
            if 10 <= int(ciphertext[i-1: i+1]) <= 25:
                if i == 1:
                    dp[i] = 2
                else:
                    dp[i] = dp[i - 1] + dp[i - 2]
            else:
                dp[i] = dp[i - 1]

        return dp[n - 1]

空间复杂度为O(n)

解法二-数字求余

优化空间复杂度可以从字符串的存储空间和动态规划数组入手

利用求余和求整运算，从右向左进行动态规划的计算，空间复杂度降至O(1)

class Solution:
    def crackNumber(self, ciphertext: int) -> int:
        a = b = 1
        y = ciphertext % 10
        while ciphertext > 9:
            ciphertext //= 10
            x = ciphertext % 10
            temp = 10 * x + y
            if 10 <= temp <= 25:
                c = a + b
            else:
                c = a
            a, b = c, a
            y = x
        return a