【中等】数字字符串转换为字母组合的种数－Java：解法一

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package live.every.day.ProgrammingDesign.CodingInterviewGuide.RecursionAndDynamicPrograming; /** * 数字字符串转换为字母组合的种数 * * 【题目】 * 给定一个字符串str，str全部由数字字符组成，如果str中某一个或某相邻两个字符组成的子串值在1~26之间，则这个子串可以转换 * 为一个字母。规定"1"转换为"A"，"2"转换为"B"，"3"转换为"C"..."26"转换为"Z"。写一个函数，求str有多少种不同的转换结 * 果，并返回种数。 * * 【难度】 * 中等 * * 【解答】 * 暴力递归的方法。假设str的长度为N，先定义递归函数p(i)(O≤i≤N)。p(i)的含义是str[0..i-1]己经转换完毕，而str[i.N-1] * 还没转换的情况下，最终合法的转换种数有多少并返回。特别指出，p(N)表示str[0..N-1](也就是str的整体)都己经转换完，没有 * 后续的字符了，那么合法的转换种数为1，即p(N)=1。那么p(i)如何计算呢？只有以下4种情况。 * 如果i=N。根据上文对p(N)=1的解释，直接返回1。 * 如果不满足情况1，又有str[i]='0'。str[0..i-1]已经转换完毕，而str[i..N-1]此时又以'0'开头，str[i..N-1]无论怎样 * 都不可能合法转换，所以直接返回0。 * 如果不满足情况1和情况2，说明str[i]属于'1~9'，str的可以转换为'A~I'，那么p(i)的值一定包含p(i+1)的值，即p(i)=p(i+l)。 * 如果不满足情况1和情况2，说明str[i]属于'1~9'，如果又有str[i..i+l]在'10~26'之间，str[i..i+1]可以转换为'J~Z'， * 那么p(i)的值一定也包含p(i+2)的值，即p(i)+=p(i+2)。 * * 具体过程请参看如下代码中的num1方法。 * * @author Created by LiveEveryDay */ public class NumStr2LetterCombination1 { public static int num1(String str) { if (str == null || str.equals("")) { return 0; } char[] chs = str.toCharArray(); return process(chs, 0); } private static 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; } public static void main(String[] args) { String str = "1111"; System.out.printf("The num is: %d", num1(str)); } } // ------ Output ------ /* The num is: 5 */