算法|leetcode把数字翻译成字符串算法|python

题目描述：给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法
示例：
输入: 12258
输出: 5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
分析：回溯法：看到这个题，我首先想到的是回溯法，回溯法会将每一种可能尝试一遍。我们将数字转换为字符串后，每一次我们都可以取其中的第一个字符或者前两个字符，判断字符整数对应的字母。并将字符串减去选中的字符
动态规划：这个题目也可以利用动态规划解决。假设f(x)表示以第x个数结尾的前缀对应的方案总数，那么对于第i个位置而言，如果它可以和前一个数字组合，组成的数字在10到25之间，那么f(i)=f(i-1)+f(i-2), 否则f(i)=f(i-1)
代码：回溯：

def translateNum(num): s = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'] res = [] l = str(num) length = len(l)def solve(s, tar, temp, curr_res): if len(temp) == length:# 已经匹配到末尾 res.append(curr_res[:]) return for i in range(0, 2): if i == 0:# 选取一个字符 c = tar[0] curr_res += s[int(c)] solve(s, tar[1:], temp+c, curr_res+s[int(c)]) else:# 选取两个字符 if len(tar) < 2: continue c = tar[0] + tar[1] if int(c) > 25 or int(c) < 10:# 判断两个字符组合而成的数字是否在10到25之间 continue solve(s, tar[2:], temp+c, curr_res+s[int(c)])solve(s, l, '', '')return len(res)

【算法|leetcode把数字翻译成字符串】动态规划：

def translateNum(num): res = [1] s = str(num) length = len(s) if length == 1: return 1if 9 < int(s[0]+s[1]) < 26: res.append(2) else: res.append(1)for i in range(2, length): c = s[i-1] + s[i] if 9 < int(c) < 26: res.append(res[i-1]+res[i-2]) else: res.append(res[i-1])return res[-1]