书籍数字字符串转换为字母组合的种数（4）0607

本文主要是介绍书籍数字字符串转换为字母组合的种数（4）0607，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

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

举例：

str=“1111”

能转换出的结果有“AAAA”,“LAA”,“ALA”,"AAL"和“LL”，返回5。

暴力递归先定义递归函数p(i)(0<=i<=N)。p(i)的含义是str[0..i-1]已经转换完毕，而str[i..N-1]还没转换的情况下，最终合法的转换种数有多少并返回。特别指出，p(N)表示str[0..N-1](也就是str的整体)都已经转换完，没有后序的字符了，那么合法的转换种数为1，即p(N)=1。比如，str=“111123”，p(4)表示str[0..3](即“1111”)已经转换完毕，具体结果是什么不重要，反正已经转换完毕并且不可以变，没转换的部分是str[4..5](即“23”)，可转换的为“BC”或“W”只有两种，所以p(4)=2。p(6)表示str整体已经转换完毕，所以p(6)=1。那么p(i)如何计算呢？只有以下4中情况。
1、如果i==N，根据上文对P(N)=1的解释，直接返回1.

2、如果不满足情况1，又有srt[i]==‘0’，str[0..i-1]已经转换完毕，而str[i..N-1]此时又以‘0’开头，str[i..N-1]无论怎样都不可能合法转换，所以直接返回0。

3、如果不满足情况1和情况2，说明str[i]属于“1~9”，str[i]可以转化为"A"-“I”,那么p(i)的值一定包含p(i+1)的值，即p(i) = p(i+1)。

4、如果不满足情况1和情况2，说明str[i]属于‘1’-‘9’，如果又有str[i..i+1]在“10”~“26”之间，str[i..i+1]可以转换为‘J’-‘Z’，那么p(i)的值一定也包含p(i+2)的值，即p(i)+=p(i+2).

public int num1(String str){if(str == null || str.equals("")){return 0;}char[] chs = str.toCharArray();return process(chs,0);
}public int process(char[] chs,int i){if(i == chs.length){return 1;}if(chs[i] == '0'){return 0;}int res = process(chs,i+1);if(i+1 < chs.length && (chs[i] - '0') * 10 + chs[i+1] -'0' < 27){res += process(chs,i+2);}return res;
}

这篇关于书籍数字字符串转换为字母组合的种数（4）0607的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---