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

分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.RecursionAndDynamicPrograming; /** * 数字字符串转换为字母组合的种数 * * 【题目】 * 给定一个字符串strstr全部由数字字符组成如果str中某一个或某相邻两个字符组成的子串值在1~26之间则这个子串可以转换 * 为一个字母。规定1转换为A2转换为B3转换为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种情况。 * 如果iN。根据上文对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~9str的可以转换为A~I那么p(i)的值一定包含p(i1)的值即p(i)p(il)。 * 如果不满足情况1和情况2说明str[i]属于1~9如果又有str[i..il]在10~26之间str[i..i1]可以转换为J~Z * 那么p(i)的值一定也包含p(i2)的值即p(i)p(i2)。 * * 具体过程请参看如下代码中的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 */