暴力递归——从左往右的尝试模型1，Facebook面试真题，_规定1和a对应,2和b对应

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

我们先来分析下题目：

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

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

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

下面我们具体分析：

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

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

3）当前位置是1字符，i+1位置无论任何字符，i和i+1连起来都不会超过26，所以又有两种可能。第一种：i位置单独转换，去i+1位置递归；第二种：i和i+1一起转换，去i+2位置递归。

4）当前位置是2字符，如果i+1位置的字符是在[0~6]，i和i+1可以一起转换，去i+2位置递归；否则，只能i单独转换，去i+1位置递归。

给大家画个图：

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

package com.harrison.class12;

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

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

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

package com.inspect.inspect100;

/**
 * @author Harrison
 * @create 2022-05-09-14:55
 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
 */
public class T068_ConvertToLetterString {
    public static int convert1(String s){
        if(s==null || s.length()==0){
            return 0;
        }
        char[] str=s.toCharArray();
        return process1(str,0);
    }

    public static int process1(char[] str,int i){
        if(i== str.length){
            return 1;
        }
        if(str[i]=='0'){
            return 0;
        }
        int ans=process1(str,i+1);
        if(i+1<str.length && ((str[i]-'0')*10+str[i+1]-'0'<27)){
            ans+=process1(str,i+2);
        }
        return ans;
    }

    public static int dp(String s){
        if(s==null || s.length()==0){
            return 0;
        }
        char[] str=s.toCharArray();
        int N=str.length;
        int[] dp=new int[N+1];
        dp[N]=1;
        for(int i=N-1; i>=0; i--){
            if(str[i]!='0'){
                int ans=dp[i+1];
                if(i+1<str.length && ((str[i]-'0')*10+str[i+1]-'0'<27)){
                    ans+=dp[i+2];
                }
                dp[i]=ans;
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        String test="11111";
        int ans1=convert1(test);
        int ans2=dp(test);
        System.out.println(ans1);
        System.out.println("======");
        System.out.println(ans2);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60