We are so excited about the future.
未来可期。
问题描述
来源：牛客题霸第127题
难度：中等
给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。
示例1
"1AB2345CD","12345EF"
"2345"
备注：
1≤∣str1∣,∣str2∣≤5000
动态规划解决
注意这题求的是最长公共子串，不是最长公共子序列，子序列可以是不连续的，但子串一定是连续的。
定义dp[i][j]表示字符串str1中第i个字符和str2种第j个字符为最后一个元素所构成的最长公共子串。如果要求dp[i][j]，也就是str1的第i个字符和str2的第j个字符为最后一个元素所构成的最长公共子串，我们首先需要判断这两个字符是否相等。
如果不相等，那么他们就不能构成公共子串，也就是
dp[i][j]=0;
如果相等，我们还需要计算前面相等字符的个数，其实就是dp[i-1][j-1]，所以dp[i][j]=dp[i-1][j-1]+1;
有了递推公式，代码就比较简单了，我们使用两个变量，一个记录最长的公共子串，一个记录最长公共子串的结束位置，最后再对字符串进行截取即可，来看下代码
1public String LCS(String str1, String str2) {
2 int maxLenth = 0;//记录最长公共子串的长度
3 //记录最长公共子串最后一个元素在字符串str1中的位置
4 int maxLastIndex = 0;
5 int[][] dp = new int[str1.length() + 1][str2.length() + 1];
6 for (int i = 0; i < str1.length(); i++) {
7 for (int j = 0; j < str2.length(); j++) {
8 //递推公式，两个字符相等的情况
9 if (str1.charAt(i) == str2.charAt(j)) {
10 dp[i + 1][j + 1] = dp[i][j] + 1;
11 //如果遇到了更长的子串，要更新，记录最长子串的长度，
12 //以及最长子串最后一个元素的位置
13 if (dp[i + 1][j + 1] > maxLenth) {
14 maxLenth = dp[i + 1][j+1];
15 maxLastIndex = i;
16 }
17 } else {
18 //递推公式，两个字符不相等的情况
19 dp[i + 1][j+1] = 0;
20 }
21 }
22 }
23 //最字符串进行截取，substring(a,b)中a和b分别表示截取的开始和结束位置
24 return str1.substring(maxLastIndex - maxLenth + 1, maxLastIndex + 1);
25}
时间复杂度：O（m*n），m和n分别表示两个字符串的长度
空间复杂度：O（m*n）
代码优化，把二维数组变为一维数组
1public String LCS(String str1, String str2) {
2 int maxLenth = 0;//记录最长公共子串的长度
3 //记录最长公共子串最后一个元素在字符串str1中的位置
4 int maxLastIndex = 0;
5 int[] dp = new int[str2.length() + 1];
6 for (int i = 0; i < str1.length(); i++) {
7 //注意这里是倒叙
8 for (int j = str2.length() - 1; j >= 0; j--) {
9 //递推公式，两个字符相等的情况
10 if (str1.charAt(i) == str2.charAt(j)) {
11 dp[j + 1] = dp[j] + 1;
12 //如果遇到了更长的子串，要更新，记录最长子串的长度，
13 //以及最长子串最后一个元素的位置
14 if (dp[j + 1] > maxLenth) {
15 maxLenth = dp[j + 1];
16 maxLastIndex = i;
17 }
18 } else {
19 //递推公式，两个字符不相等的情况
20 dp[j + 1] = 0;
21 }
22 }
23 }
24 //最字符串进行截取，substring(a,b)中a和b分别表示截取的开始和结束位置
25 return str1.substring(maxLastIndex - maxLenth + 1, maxLastIndex + 1);
26}
时间复杂度：O（m*n），m和n分别表示两个字符串的长度
空间复杂度：O（n），只需要一个一维数组即可
总结
这题比较简单，很久以前也讲过这题370，最长公共子串和子序列，之前只是返回一个具体的数字即可，而这题需要返回具体的公共子串，多了一步。
联系客服
