【中等】数字字符串转换为字母组合的种数－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有多少种不同的转换结 * 果，并返回种数。 * * 【难度】 * 中等 * * 【解答】 * 以上过程中，p(i)最多可能会有两个递归分支p(i+1)和p(i+2)，一共有N层递归，所以时间复杂度为0(2^N)，额外空间复杂度就是 * 递归使用的函数栈的大小为O(N)。但是研究一下递归函数p就会发现，p(i)最多依赖p(i+1)和p(i+2)的值，这是可以从后往前进行 * 顺序计算的，也就是先计算p(N)和p(N-1)，然后根据这两个值计算p(N-2)，再根据p(N-1)和p(N-2)计算p(N-3)，最后根据p(1) * 和p(2)计算出p(O)即可，类似斐波那契数列的求解过程，只不过斐波那契数列是从前往后计算的，这里是从后往前计算而己。 * 具体过程请参看如下代码中的num2方法。 * 因为是顺序计算，所以num2方法的时间复杂度为O(N)，同时只用了cur、next和tmp进行滚动更新，所以额外空间复杂度为O(1)。 * 但是本题并不能像斐波那契数列问题那样用矩阵乘法的优化方法将时间复杂度优化到O(logN)，这是因为斐波那契数列是严格的 * f(i)=f(i-1)+f(i-2)，但是本题并不严格，str[i]的具体情况决定了p(i)是等于0还是等于p(i+l)，还是等于p(i+1)+p(i+2)。 * 有状态转移的表达式不可以用矩阵乘法将时间复杂度优化到O(logN)。但如果str只由字符'1’和字符'2'组成，比如 * "12121121212122”，那么就可以使用矩阵乘法的方法将时间复杂度优化为O(logN)。因为str[i]都可以单独转换成字母， * str[i..i+1]也都可以一起转换成字母，此时一定有p(i)=p(i+1)+p(i+2)。总之，可以使用矩阵乘法的前提是递归表达式不会 * 发生转移。 * * @author Created by LiveEveryDay */ public class NumStr2LetterCombination2 { public static int num2(String str) { if (str == null || str.equals("")) { return 0; } char[] chs = str.toCharArray(); int cur = chs[chs.length - 1] == '0' ? 0 : 1; int next = 1; int tmp = 0; for (int i = chs.length - 2; i >= 0; i--) { if (chs[i] == '0') { next = cur; cur = 0; } else { tmp = cur; if ((chs[i] - '0') * 10 + chs[i + 1] - '0' < 27) { cur += next; } next = tmp; } } return cur; } public static void main(String[] args) { String str = "1111"; System.out.printf("The num is: %d", num2(str)); } } // ------ Output ------ /* The num is: 5 */