难度: Medium
现有一串神秘的密文 ciphertext，经调查，密文的特点和规则如下：
请根据上述规则将密文 ciphertext 解密为字母，并返回共有多少种解密结果。
示例 1:
输入: ciphertext = 216612
输出: 6
解释: 216612 解密后有 6 种不同的形式，分别是 "cbggbc"，"vggbc"，"vggm"，"cbggm"，"cqggbc" 和 "cqggm"
提示：
0 <= ciphertext < 231运行时间: 36 ms
内存: 14.9 MB
class Solution:
def translateNum(self, num: int) -> int:
memo = dict()
def dp(i):
if i in memo:
return memo[i]
if i <= 0:
return 1
if 10 <= int(str(num)[i-1] + str(num)[i]) <= 25:
memo[i] = dp(i-1) + dp(i-2)
else:
memo[i] = dp(i-1)
return memo[i]
return dp(len(str(num))-1)
这个题解通过动态规划的方式解决问题。首先将数字转换为字符串，以便于访问每一位数字。定义dp(i)为从字符串的第i位到最后一位可以有多少种解码方式。如果当前位和下一位组成的数字在10到25之间，那么这两位可以被解码为一个字符，因此dp(i) = dp(i-1) + dp(i-2)，即考虑当前位单独解码和与下一位一起解码的情况。如果不在这个范围内，只能单独解码，因此dp(i) = dp(i-1)。递归的基情况是当i小于等于0时，返回1，表示至少有一种解码方式。最终，dp(len(str(num))-1)给出了从第0位到最后一位的解码方式总数。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def translateNum(self, num: int) -> int:
memo = dict() # 用来存储已经计算过的结果
def dp(i):
if i in memo: # 如果已计算过这个位置，直接返回结果
return memo[i]
if i <= 0: # 达到字符串起始位置，返回1表示一种解码方式
return 1
if 10 <= int(str(num)[i-1] + str(num)[i]) <= 25: # 如果两位数字可以合并解码
memo[i] = dp(i-1) + dp(i-2) # 加上合并解码的结果
else:
memo[i] = dp(i-1) # 不能合并，只考虑单独解码
return memo[i]
return dp(len(str(num))-1) # 从最后一位开始解析，返回总的解码方式数
在这个动态规划的解法中，基情况设置为当`i<=0`时返回1，是为了处理解码过程的边界情况。当`i = 0`时，表示我们正在解析字符串的第一个数字，此时应该返回1因为至少存在一种解码方式（即当前数字自身）。当`i < 0`时，通常是因为前两个数字组成了一个有效的10到25之间的数字，我们需要为此“多出来的”位置返回1，以正确计算总的解码方式数。这样的设置简化了代码逻辑，允许在计算dp(i)时，不需要对i-2做特殊边界检查。
题解中确实提到了数字组合在10到25之间可以解码，但对于数字0的处理需要特别注意。在这种解码规则中，0不能单独解码为一个字符（没有与之对应的字母），它必须与前一个数字组合来进行解码（即组成10或20）。如果0作为单独数字存在，或不与1或2组合，则这样的数字字符串实际上是不可解的，会导致解码方式为0。在实际实现中，应该加入检查以确保不会尝试解码一个孤立的0或不正确组合的数字。
题解中使用的是递归方式，具体是通过递归函数`dp(i)`来实现。尽管是递归形式，但由于引入了记忆化（使用`memo`字典来存储已计算的结果），使得每个子问题只计算一次。这种结合了递归和记忆化的方法有效地减少了重复计算，避免了纯递归可能导致的大量重复调用和栈溢出问题，因此虽然底层是递归调用，实际效果和迭代方法类似。
在动态规划的实现中，边界条件的设置十分关键。对于字符串的最后一位数字，它可以独立解码（除非它是0且不与前一位数字组成有效的组合），因此`dp(len(str(num))-1)`的初始值通常是1，表示最后一位至少有一种解码方式。对于最后两位数字，如果它们组成的数字在10到25之间，还需要将`dp(len(str(num))-2)`的值设置为2（前提是这两位符合解码条件），否则为1（只能单独解码每一位）。这些边界条件确保了从字符串的末尾向前进行动态规划时，每一步的解码方式计数是正确的。