规定A对应1，B对应2... Z对应26
举个栗子： 111就可以转化为 'AAA', 'KA', 'AK'
给定一个只有数字字符组成的str，返回一共有多少种转化结果
暴力递归思路：
-
可以把这个字符串想成0 ~ N-1位，当在第index位的时候，只考虑N-index的方法，相加即为index位的方法。f(n) = f(n-1) + f(n-2)
-
确定递归出口，
-
当index到达末尾，即无其他方法，计为 1
-
当index位置上为“0”时，即方案错误，无法转化，计为0
（index可以看做头，以"0"为首部的数字没办法转化）
-
-
确定递推式
- 单转：直接index+1
- 双转：确定index+1不越界，且，这两位数小于27
- 单转 + 双转，即为所有的可能
DP思路：
- 构建dp，由于字符串转化数是根据index位置决定的，线性的，只需要构建一维数组，为什么是N+1，因为当index走到最后（越界）时，只有一种转化方法，dp[N] = 1
- 判断依赖关系：index依赖于index+1的方法，所以从后往前填充dp
- 填充dp
- 判断情况，头为"0"时，决策错误，无转化方法
- 单转：直接加
- 双转：判断是否符合情况再加（我这样写比较帅，但是多进行了一次赋值操作）
- 返回值：index从0开始
def translate_str(string):
if not string or len(string) == 0: # 边界条件
return 0
def process(string, index):
# 只考虑index之后的转化，0~index不需要考虑
if len(string) == index:
return 1
if string[index] == "0": # 之前做的决定有问题
return 0
# 存在两种情况：单转和双转
# 单转
ways = process(string, index+1)
# 双转，index+1不越界，且，string[index, index+2]小于27
if index+1 < len(string) and int(string[index:index+2]) < 27:
ways += process(string, index + 2)
return ways
return process(string, 0)
def dp_translate_str(string):
if not string or len(string) == 0: # 边界条件
return 0
N = len(string)
dp = [0 for _ in range(N+1)]
dp[N] = 1
for i in range(N-1, -1, -1):
if string[i] == "0": # 当为0时，决策错误
continue
dp[i] = dp[i+1]
dp[i] += dp[i+2] if i + 1 < N and int(string[i:i+2]) < 27 else 0
return dp[0]
print(translate_str("11111")) # 8
print(translate_str("12313")) # 6
print(translate_str("13035643242311")) # 0，里面有个30，没办法转
print(dp_translate_str("11111"))
print(dp_translate_str("12313"))
print(dp_translate_str("13035643242311"))
题目同：可以自己练习一下
剑指 Offer 46. 把数字翻译成字符串
https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/