数字字符串转化为字母组合的种数

题目

　　给定一个字符串str，str全部由数字字符组成，如果str中某一个或者某相邻两个字符组成的子串在1~26之间，则这个子串可以转换为一个字母。规定“1”转换为“A”，“2”转换为“B”……“26”转换为“Z”。求str有多少种不同的转换结果。

举例

　　str = “1111” 
　　能转换成的结果有“AAAA”，“LAA”，“ALA”，“AAL”和“LL”，返回5。 
　　str = “01”，“0”没有对应的字母，返回0。

基本思路
1.暴力递归的方法。定义递归函数p(i)，p(i)表示只转换字符串的i～N-1部分（N表示字符串的长度），一共有多少种转换结果。接下来便可以进行递归求解：

如果i == N，p(N)表示没有任何字符需要转换，返回 1。

如果str[i] == ‘0’，因为以0开头的子串都能进行转换，所以返回 0。

如果不满足条件1和2，说明此时str[i]在 ‘1’ 到 ‘9’ 之间，这个时候str[i]能转换的种数至少包含p(i+1)。如果str[i]和str[i+1]的组合又在 ‘10’ 到 ‘26’ 之间，则str[i]能转换的种数还要包含p(i+2)，即ｐ(i) = p(i+1) 或者p(i) = p(i+1) + p(i+2)。
2.动态规划的方法。由上述可知，p(i)的值最多依赖于p(i+1)和p(i+2)，即p(i) = p(i+1) (+ p(i+2))，这就是典型的斐波那契问题的变形题，只不过这里是从后往前计算而已。

"""暴力递归"""def num1(str1):if str1 == None or str1 == '':return 0return process(str1,0)def process(str1,i):if i == len(str1):return 1if str1[i] == '0':return 0res = process(str1,i+1)if i+1 < len(str1) and ((int(str1[i]))*10 + int(str1[i+1])< 27:res += process(str1,i+2)return res"""动态规划"""def num2(str1):if str1 == None or str1 == '':return 0if str1[-1] != 0:cur = 1else:cur = 0next_ = 1for i in range(len(str1)-2,-1,-1):if str1[i] == '0':next_ = curcur = 0else:tmp = curif int(str1[i])*10 + int(str1[i+1])< 27:cur += next_next_ = tmpreturn cur

 

 

 

总结

以上是生活随笔为你收集整理的数字字符串转化为字母组合的种数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。