【算法】【递归与动态规划模块】两个字符串的最长公共子数组

前言

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

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

问题介绍

原问题
给定str1和str2两个字符串，求两个字符串的最长公共子数组，不是最长公共序列。
如：
str1:1AB2345CD str2:12345EF
结果：2345

解决方案

参考：https://swzhao.blog.csdn.net/article/details/127585231

原问题：
1、设计dp[i][j] 代表 最长子数组以str1[i]和str2[j]结尾，最长子数组的长度
2、dp[i][j]的递推关系:如果需要求以str1[i]和str2[j]结尾的最长子数组长度，则首先判断str1[i] 和str2[j]是否相等，如果不相等，则dp[i][j]为0，如果相等，则dp[i][j] = dp[i-1][j-1] + 1

代码编写

java语言版本

原问题：
递归方法：

   
    /**
     * 获取最长子数组
     * @param str1
     * @param str2
     * @return
     */
    public static String getMaxSubArrCP(String str1, String str2) {
        if (str1 == null || str1.length() == 0
                || str2 == null || str2.length() == 0) {
            return null;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int[][] dp = new int[chars1.length][chars2.length];
        int[] maxIJ = getDpCP(chars1, chars2, dp);
        // 将最大值的坐标拿出来
        int maxI = maxIJ[0];
        int maxJ = maxIJ[1];
        int maxLen = chars1.length > chars2.length ? chars1.length : chars2.length;
        int index = 0;
        char[] res = new char[maxLen];
        while (maxI >= 0 && maxJ >= 0) {
            if (chars1[maxI] == chars2[maxJ]) {
                res[index++] = chars1[maxI];
                maxI--;
                maxJ--;
            }else {
                break;
            }
        }
        CommonUtils.reverseChar(res, 0, index);
        return String.valueOf(res, 0, index);
    }

    /**
     * 生成dp矩阵
     * 返回最大值的两个坐标
     * @param chars1
     * @param chars2
     * @return
     */
    private static int[] getDpCP(char[] chars1, char[] chars2, int[][] dp) {
        // dp[i][j] 表示，chars[i]为底和chars[2]为底的公共子数组长度，区别于chars1[i]为底的，chars2[j]为底的数组的公共子数组长度
        //int[][] dp = new int[chars1.length][chars2.length];
        int maxI = 0;
        int maxJ = 0;
        int max = Integer.MIN_VALUE;
        dp[0][0] = chars1[0] == chars2[0] ? 1 : 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = dp[i-1][0] == 1 || chars1[i] == chars2[0] ? 1 : 0;
        }
        for (int j = 1; j < dp[0].length; j ++) {
            dp[0][j] = dp[0][j-1] == 0 || chars1[0] == chars2[j] ? 1 : 0;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (chars1[i] != chars2[j]) {
                    dp[i][j] = 0;
                }else {
                    int count = 1;
                    int iIndex = i;
                    int jIndex = j;
                    while (iIndex >= 0 && jIndex >= 0) {
                        if (chars1[iIndex] == chars2[jIndex]) {
                            count++;
                            iIndex--;
                            jIndex--;
                        }else {
                            break;
                        }
                    }
                    if (count > max) {
                        maxI = i;
                        maxJ = j;
                        max = count;
                    }
                    dp[i][j] = count;
                }
            }
        }
        return new int[]{maxI, maxJ};
    }

    /**
     * 降低空间复杂度版本
     * @param str1
     * @param str2
     * @return
     */
    private static String getMaxSubArrCPReduceMem(String str1, String str2) {
        if (str1 == null || str1.length() == 0
                || str2 == null || str2.length() == 0) {
            return null;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int max = Integer.MIN_VALUE;
        int maxI = 0;
        int maxJ = 0;
        int i = 0;
        int j = chars2.length-1;
        int count = chars1.length + chars2.length -1;
        while (count-- >= 0) {
            int temI = i;
            int temj = j;
            int temMax = 0;
            int temMaxI = 0;
            int temMaxJ = 0;
            int last = 0;
            while (temI < chars1.length && temj < chars2.length) {
                if (chars1[temI] == chars2[temj]) {
                    last++;
                }else {
                    last = 0;
                }
                if (last > temMax) {
                    temMax = last;
                    temMaxI = temI;
                    temMaxJ = temj;
                }
                temI++;
                temj++;
            }
            if (temMax > max) {
                maxI = temMaxI;
                maxJ= temMaxJ;
                max= temMax;
            }
            if (j != 0) {
                // 还在第一行
                j--;
            }else {
                i++;
            }
        }
        // 将最大值的坐标拿出来
        int maxLen = chars1.length > chars2.length ? chars1.length : chars2.length;
        int index = 0;
        char[] res = new char[maxLen];
        while (maxI >= 0 && maxJ >= 0) {
            if (chars1[maxI] == chars2[maxJ]) {
                res[index++] = chars1[maxI];
                maxI--;
                maxJ--;
            }else {
                break;
            }
        }
        CommonUtils.reverseChar(res, 0, index);
        return String.valueOf(res, 0, index);
    }

    public static void main(String[] args) {
        getMaxSubArrCPReduceMem("1AB2345CD", "12345EF");
    }
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

首先想要理解这道题，可以参考一下

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

只读感悟即可，如果我没有感悟上一道题，这道题是不会做的，首先上道题把规律应该讲的比较清楚，这道题也是一道最优解不是dp最后一个元素类型的问题，那么很显然，同样的感觉 以每一个元素为底时的结果有可能不包含该元素，这个时候就需要强制将当前元素变成底来做动态规划，当我想到这个思路的时候这道题基本上就是秒了。

这里提一句降低空间复杂度的版本，这个最优解为什么能够产生呢？是因为子数组都是连续的，不像子序列，并且子数组str1和str2元素都是相等的，所以这个最优解的代表仅仅只需要子数组的头或者尾就可以了，因此整个过程就是求最优解的头或者尾就行了。

写在最后

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