深入解析暴力递归：从左至右的尝试模型，真实Facebook面试题目

题目&＃xff1a;规定1和A对应、2和B对应、3和C对应…那么一个数字字符串比如"111”就可以转化为&＃xff1a;&＃39;AAA"、 “KA"和"AK”。给定一个只有数字字符组成的字符串str&＃xff0c;返回有多少种转化结果

我们先来分析下题目&＃xff1a;

数字1对应字母A&＃xff0c;2对应B&＃xff0c;…一直到26对应Z。数字0是没有字符与之对应的&＃xff0c;也就是说&＃xff0c;如果碰到0是没有转换结果的。

仔细分析这道题&＃xff0c;会发现在暴力递归中&＃xff0c;这是一个从左往右的尝试模型。

什么是从左往右的尝试模型呢&＃xff0c;之前写过的打印一个字符串的全部排列和子序列都是这种模型&＃xff0c;简单来说&＃xff0c;就是从左往右一个一个暴力尝试。

下面我们具体分析&＃xff1a;

1&＃xff09;首先考虑base case&＃xff0c;如果i位置来到字符串的终止位置&＃xff0c;有两种可能&＃xff0c;字符串没有字符了&＃xff0c;所以返回空字符&＃xff0c;算是一种结果&＃xff1b;或者之前已经有转换好的答案&＃xff0c;所以返回一个结果。

2&＃xff09;如果当前位置的字符是在3~9之间&＃xff0c;i&＃43;1位置无论是什么字符&＃xff0c;i和i&＃43;1连起来都会超过26&＃xff0c;所以这种情况下&＃xff0c;i位置单独转换&＃xff0c;然后去i&＃43;1位置递归。

3&＃xff09;当前位置是1字符&＃xff0c;i&＃43;1位置无论任何字符&＃xff0c;i和i&＃43;1连起来都不会超过26&＃xff0c;所以又有两种可能。第一种&＃xff1a;i位置单独转换&＃xff0c;去i&＃43;1位置递归&＃xff1b;第二种&＃xff1a;i和i&＃43;1一起转换&＃xff0c;去i&＃43;2位置递归。

4&＃xff09;当前位置是2字符&＃xff0c;如果i&＃43;1位置的字符是在[0~6]&＃xff0c;i和i&＃43;1可以一起转换&＃xff0c;去i&＃43;2位置递归&＃xff1b;否则&＃xff0c;只能i单独转换&＃xff0c;去i&＃43;1位置递归。

给大家画个图&＃xff1a;

当然&＃xff0c;博主一开始写这种题也不会有这么清晰的思路&＃xff0c;也只能是写一步看一步&＃xff0c;发现写不下去了&＃xff0c;就检查是不是缺少变量啥的导致无法写下去。总之就是要硬写&＃43;多写&＃xff0c;哈哈哈。

package com.harrison.class12;public class Code05_ConvertToLetterString {// 0~i-1位置已经转换好了&＃xff0c;做好决定了&＃xff0c;不用再考虑// i及其往后的位置有多少种转换的结果public static int process1(char[] str,int i) {// i来到终止位置&＃xff0c;没有字符了&＃xff0c;转换为空字符// 要么认为0~i-1已经转换好了&＃xff0c;返回一个点数if(i&＃61;&＃61;str.length) {return 1;}// i没有到终止位置if(str[i]&＃61;&＃61;&＃39;0&＃39;) {// 0没有对应的字符return 0;}// i没有到终止位置 && i位置不是0字符// i位置是1字符&＃xff0c;i&＃43;1位置无论是什么字符都不会超过26&＃xff0c;都可以转换if(str[i]&＃61;&＃61;&＃39;1&＃39;) {int res&＃61;process1(str, i&＃43;1);// i位置自己单独转换&＃xff0c;后续有多少种方法if(i&＃43;1<str.length) {res&＃43;&＃61;process1(str, i&＃43;2);// i和i&＃43;1位置一起转换&＃xff0c;后续有多少种方法}return res;}// i位置是2字符&＃xff0c;如果i&＃43;1位置的字符是0~6&＃xff0c;i和i&＃43;1就可以一起转换&＃xff0c;然后i&＃43;2位置接着递归// 否则只能i位置自己转换&＃xff0c;然后i&＃43;1位置接着递归if(str[i]&＃61;&＃61;&＃39;2&＃39;) {int res&＃61;process1(str, i&＃43;1);if(i&＃43;1<str.length && (str[i&＃43;1]>&＃61;&＃39;0&＃39; && str[i&＃43;1]<&＃61;&＃39;6&＃39;)) {res&＃43;&＃61;process1(str, i&＃43;2);}return res;}return process1(str, i&＃43;1);}public static int convert1(String s) {if(s&＃61;&＃61;null || s.length()&＃61;&＃61;0) {return 0;}char[] str&＃61;s.toCharArray();return process1(str, 0);}public static void main(String[] args) {String test&＃61;"111";System.out.println(convert1(test));}
}

另外据说这道题是曾经Facebook的面试真题哦&＃xff0c;你搞懂了吗

上面的暴力尝试并不是最优的&＃xff0c;所以在这基础上改动态规划也会比较麻烦&＃xff0c;下面的写法的暴力尝试比上面的好。

package com.inspect.inspect100;/*** &＃64;author Harrison* &＃64;create 2022-05-09-14:55* &＃64;motto 众里寻他千百度&＃xff0c;蓦然回首&＃xff0c;那人却在灯火阑珊处。*/
public class T068_ConvertToLetterString {public static int convert1(String s){if(s&＃61;&＃61;null || s.length()&＃61;&＃61;0){return 0;}char[] str&＃61;s.toCharArray();return process1(str,0);}public static int process1(char[] str,int i){if(i&＃61;&＃61; str.length){return 1;}if(str[i]&＃61;&＃61;&＃39;0&＃39;){return 0;}int ans&＃61;process1(str,i&＃43;1);if(i&＃43;1<str.length && ((str[i]-&＃39;0&＃39;)*10&＃43;str[i&＃43;1]-&＃39;0&＃39;<27)){ans&＃43;&＃61;process1(str,i&＃43;2);}return ans;}public static int dp(String s){if(s&＃61;&＃61;null || s.length()&＃61;&＃61;0){return 0;}char[] str&＃61;s.toCharArray();int N&＃61;str.length;int[] dp&＃61;new int[N&＃43;1];dp[N]&＃61;1;for(int i&＃61;N-1; i>&＃61;0; i--){if(str[i]!&＃61;&＃39;0&＃39;){int ans&＃61;dp[i&＃43;1];if(i&＃43;1<str.length && ((str[i]-&＃39;0&＃39;)*10&＃43;str[i&＃43;1]-&＃39;0&＃39;<27)){ans&＃43;&＃61;dp[i&＃43;2];}dp[i]&＃61;ans;}}return dp[0];}public static void main(String[] args) {String test&＃61;"11111";int ans1&＃61;convert1(test);int ans2&＃61;dp(test);System.out.println(ans1);System.out.println("&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;");System.out.println(ans2);}
}