Java日常练习题,每天进步一点点(28)

题目：给定两个字符串，找到这两个字符串中最长的公共连续子字符串。

示例1：

输入: str1 = "ABCD" ，str2 = "CBCE"
输出: "BC"

示例2：

输入: str1 = "ABC" ，str2 = "DEF"
输出: ""

分析：题目要求找到两个字符串的最长公共连续子字符串，我们可以通过动态规划算法来解决此类问题。具体思路是，定义一个二维数组dp，其中dp[i][j]表示字符串str1的第i个字符和字符串str2的第j个字符之前的最长公共子串的长度。若当前两个字符相等，则可以推出状态转移方程dp[i][j] = dp[i-1][j-1] + 1，否则dp[i][j] = 0。最后找到数组中的最大值，并根据长度截取公共子串即可。

代码示例：

public static String longestCommonSubString(String str1, String str2) {
    int[][] dp = new int[str1.length()+1][str2.length()+1];
    int maxLen = 0;
    int end = 0;
    for (int i = 1; i <= str1.length(); i++) {
        for (int j = 1; j <= str2.length(); j++) {
            if (str1.charAt(i-1) == str2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            if (dp[i][j] > maxLen) {
                maxLen = dp[i][j];
                end = i-1;
            }
        }
    }
    return str1.substring(end-maxLen+1, end+1);
}

代码说明：本代码在二维数组dp初始化时为了方便后续处理，二维数组第一维和第二维分别加了1，最后找到数组中的最大值并根据长度截取公共子串时需要考虑边界情况。

示例1解析：在str1="ABCD" 和 str2="CBCE"的情况下，根据动态规划算法得到的dp数组如下所示，其中11表示B和B的公共连续子串长度为1，22表示BC和BC的公共连续子串长度为2：

		C	B	C	E
	0	0	0	0	0
A	0	0	0	0	0
B	0	0	1	2	0
C	0	1	0	0	1
D	0	0	0	0	0

最后找到dp数组中的最大值为22，因此返回的结果为"BC"。

示例2解析：在str1="ABC" 和 str2="DEF"的情况下，根据动态规划算法得到的dp数组如下所示，其中公共连续子串长度均为0：

		D	E	F
	0	0	0	0
A	0	0	0	0
B	0	0	0	0
C	0	0	0	0

最后找到dp数组中的最大值为0，因此返回的结果为""。