【算法】【递归与动态规划模块】判断字符串的顺序交错组成

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定str1和str2，再给一个aim，求是否aim是str1和str2的交错组成？即aim由str1和str2组成且aim中在str1中的元素之间保持str1的顺序，str2保持str2的顺序
如：
str1：AB
str2: 123
aim：A1B23
结果为true
如果aim = “A132B”
结果为false

解决方案

原问题：
递归方法：
1、首先aim的长度必须是str1的长度和str2的长度之和
2、设计三个游标i1、i2、i3,遍历aim，如果aim[i3]=str1[i1] 则i1++， 如果aim[i2] = str2[i2] 则 i2++, 如果都不相等，直接返回false,如果都相等
，则递归求[ f(i3++, i1++, i2) || f(i3++, i1, i2++)]
动态规划方法：
第一要素：
dp[i][j] 表示str1[0…i]和str2[0…j]是否能够组成aim[0…i+j+2]

代码编写

java语言版本

原问题：
递归规划：

    /**
     * 递归方法
     * @param str1
     * @param str2
     * @param aim
     * @return
     */
    public static boolean getCrossStrCP(String str1, String str2, String aim) {
        if (str1 == null || str2 == null || aim == null
                || str1.length() + str2.length() != aim.length()) {
            return false;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        char[] chars3 = aim.toCharArray();
        return processForCrossStrCP(chars1, 0, chars2, 0, chars3, 0);
    }


    /**
     * 求从str1的start1开始，str2的start2开始判断是否为aim的start3之后的交叉序列
     * @param chars1
     * @param start1
     * @param chars2
     * @param start2
     * @param chars3
     * @param start3
     * @return
     */
    private static boolean processForCrossStrCP(char[] chars1, int start1, char[] chars2, int start2, char[] chars3, int start3) {
        if (start3 >= chars3.length)
        {
            // 结束
            return true;
        }
        // 三个数组游标
        int s1 = start1;
        int s2 = start2;
        int s3 = start3;
         while (s3 <= chars3.length-1 && s1 <= chars1.length-1 && s2 <= chars2.length-1) {
            if (chars3[s3] == chars1[s1] && chars3[s3] == chars2[s2]){
                // 都相等说明两个可能性,有一个过去就行
                return processForCrossStrCP(chars1, start1+1, chars2, start2, chars3, start3+1)
                        ||processForCrossStrCP(chars1, start1, chars2, start2+1, chars3, start3+1);
            }else if (chars3[s3] == chars1[s1]) {
                s1++;
            }else if (chars3[s3] == chars2[s2]) {
                s2++;
            }else {
                // 两个都不等于说明顺序不对
                return false;
            }
            s3++;
        }
        if (s3 >= chars3.length) {
            // 说明验证结束了
            return true;
        }else {
            int indexReamin = s1 > chars1.length ? s2 : s1;
            char[] remainChar = s1 > chars1.length?  chars2 : chars1;
            while (s3 < chars3.length) {
                if (chars3[s3++] != remainChar[indexReamin++]) {
                    return false;
                }
            }
        }
        return true;
    }

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
61
62
63
64
65
66
67
68
69

动态规划：

    /**
     * 动态规划方法
     * @param str1
     * @param str2
     * @param aim
     * @return
     */
    public static boolean getFCrossStrDPCP(String str1, String str2, String aim) {
        if (str1 == null || str2 == null || aim == null
                || str1.length() + str2.length() != aim.length()) {
            return false;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        char[] chars3 = aim.toCharArray();
        boolean[][] dp = new boolean[chars1.length+1][chars2.length+1];
        dp[0][0] = true;
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = dp[i-1][0] && chars1[i-1] == chars3[i-1];
        }
        for (int j = 1; j < dp[0].length; j++) {
            dp[0][j] = dp[0][j-1] && chars2[j-1] == chars3[j-1];
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (!dp[i-1][j] && !dp[i][j-1]) {
                    dp[i][j] = false;
                }else if (dp[i-1][j] && dp[i][j-1]){
                    dp[i][j] = true;
                }else if (dp[i-1][j]){
                    dp[i][j] = chars1[i-1] == chars3[i+j-1];
                }else {
                    dp[i][j] = chars2[j-1] == chars3[i+j-1];
                }
            }
        }
        return dp[chars1.length][chars2.length];
    }



    public static void main(String[] args) {
        System.out.println(getFCrossStrDPCP("AB", "123", "1A233"));
    }
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

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题刚开始我差点方向错了，我认为aim[0…i+j+2] 中会存在 str1[0…i] 和str2[0…j]以外的元素，后来想一下，如果存在的话早就应该返回false了。
如果想通了这道题很简单，只不过第二个坎在于当aim[k] 和 str1[k1] 和str2[k2]都相等的情况下怎么办？只能枚举一下，这里就得利用递归来进行一个状态分支，比如等于str1[k1]时是否为true或者等于str2[k2]时是否为true，只要一个状态成立就可以。

接下来讲一下动态规划，动态规划可以从递归推出来，因为递归的时候我们发现入参有6个，3个定量去掉，还有三个变量，是否应该是三维的dp呢？？？很显然index1 + index2 = index3 + 2 存在一个关系所以这里不能作为三维的，只能是二维的，所以dp就推出来了。递归推动态规划的文章可以参考思考感悟：

https://swzhao.blog.csdn.net/article/details/127460219

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！