最长公共子串
题目描述
给定两个字符串str1和str2,输出两个字符串的最长公共子串，如果最长公共子串为空，输出-1。
示例1
输入"1AB2345CD","12345EF"
返回值"2345"
这条题目被归类为动态规划，于是我使用动态规划的思路写了一个算法：
/**
* longest common substring
* 动态规划算法
* dp[i][j]有两个分支
* 1. str1[i] = str2[j] dp[i][j] = dp[i][j] + 1
* 2. str1[i] != str2[j] dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
*
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
public static String LCS(String str1, String str2) {
// write code here
//零界值判断
if (str1 == null || str2 == null || (str1.isEmpty() && str2.isEmpty())) {
return "-1";
}
int str1L = str1.length();
int str2L = str2.length();
int[][] dp = new int[str1L][str2L];
Map<Integer, String> resultMap = new HashMap<>();
//初始化索引为0的值 这个是基准值
for (int i = 0; i < str1L; i++) {
boolean result = str1.charAt(i) == str2.charAt(0);
dp[i][0] = result ? 1 : 0;
resultMap.put(i * str1L, result ? str2.substring(0, 1) : "");
}
for (int j = 0; j < str2L; j++) {
boolean result = str1.charAt(0) == str2.charAt(j);
dp[0][j] = result ? 1 : 0;
resultMap.put(j, result ? str1.substring(0, 1) : "");
}
//动态规划算法
for (int i = 1; i < str1L; i++) {
for (int j = 1; j < str2L; j++) {
if (str1.charAt(i) == str2.charAt(j)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
resultMap.put(i * str1L + j, resultMap.get((i - 1) * str1L + j - 1) + str1.charAt(i));
} else {
if (dp[i][j - 1] > dp[i - 1][j]) {
dp[i][j] = dp[i][j - 1];
resultMap.put(i * str1L + j, resultMap.get(i * str1L + j - 1));
} else {
dp[i][j] = dp[i - 1][j];
resultMap.put(i * str1L + j, resultMap.get((i - 1) * str1L + j));
}
}
}
}
if(dp[str1L-1][str2L-1] <= 0){
return "-1";
}else{
return resultMap.get(str1L * (str1L - 1) + str2L - 1);
}
} 算法解析不赘述，参见 动态规划经典例题——最长公共子序列和最长公共子串
下面进入正题，当我保存提交代码后，被报错：
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为0.00%
于是我仔细拜读了其他几篇动态规划思路的解法，确认实现没啥问题啊，后面我又做了一点小优化，但是执行结果都大同小异
/**
* longest common substring
* 动态规划算法
* dp[i][j]有两个分支
* 1. str1[i] = str2[j] dp[i][j] = dp[i][j] + 1
* 2. str1[i] != str2[j] dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
*
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
public static String LCS(String str1, String str2) {
// write code here
//零界值判断
if (str1 == null || str2 == null || (str1.isEmpty() && str2.isEmpty())) {
return "-1";
}
char[] chars1 = str1.toCharArray();
char[] chars2 = str2.toCharArray();
int str1L = chars1.length;
int str2L = chars2.length;
//动态规划结果
int[][] dp = new int[str1L][str2L];
Map<Integer, String> resultMap = new HashMap<>(str1L * (str1L - 1) + str2L - 1);
//动态规划算法
for (int i = 0; i < str1L; i++) {
for (int j = 0; j < str2L; j++) {
if (chars1[i] == chars2[j]) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
resultMap.put(i * str1L + j, "" + chars1[i]);
} else {
dp[i][j] = dp[i - 1][j - 1] + 1;
resultMap.put(i * str1L + j, resultMap.get((i - 1) * str1L + j - 1) + chars1[i]);
}
} else {
if (i == 0 || j == 0) {
dp[i][j] = 0;
resultMap.put(i * str1L + j, "");
} else {
if (dp[i][j - 1] > dp[i - 1][j]) {
dp[i][j] = dp[i][j - 1];
resultMap.put(i * str1L + j, resultMap.get(i * str1L + j - 1));
} else {
dp[i][j] = dp[i - 1][j];
resultMap.put(i * str1L + j, resultMap.get((i - 1) * str1L + j));
}
}
}
}
}
if(dp[str1L-1][str2L-1] <= 0){
return "-1";
}else{
return resultMap.get(str1L * (str1L - 1) + str2L - 1);
}
} 最后我把所有无关代码都注释了，只保留了动态规划需要的循环遍历，结果耗时还是很严重：
1AB2345CD 12345EF 动态规划 LCS cost time:258800 滑动窗口 LCS1 cost time:98500
可以看出来执行效率根本不是一个量级的，所以我开始研究执行通过的算法：
/**
* 滑动窗口算法
*
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
public static String LCS1(String str1, String str2) {
// write code here
StringBuilder sb = new StringBuilder();
int start = 0, end = 1;
while (end < str1.length() + 1) {
if (str2.contains(str1.substring(start, end))) {
if (sb.length() < end - start) {
sb.delete(0, sb.length());
sb.append(str1, start, end);
}
} else {
//这个算法我曾经疑惑，假如出现start>end，程序不是会crash么
//通过debug发现，当start==end时，substring获取的是""，此时contains必然为true
//所以当start == end时，必然会走end++分支
start++;
}
end++;
}
if (sb.length() == 0) {
return "-1";
}
return sb.toString();
} 这段算法我觉得应该属于滑动窗口的范畴，start和end描述了一个窗口
- 从
str1中按照窗口截取窗口子串，检查str2中是否包含，如果包含就扩展窗口 - 如果
str2中不包含窗口子串，我们就移动窗口起始位置 sb是用来记录最大的窗口子串的，窗口最小为0个单位
这个算法精妙的地方在于窗口大小是不会缩小的，我们只需要找最大公共子串，所以一旦有某个窗口子串命中了，往后的窗口子串就不能小于上次命中的长度，所以我们在算法里可以看到当start++时必然伴随着end++，保证窗口不会变小
但是这个算法凭什么比动态规划执行效率高呢？里面用了很多Java封装的函数，很多substring操作，不管是内存还是执行效率(contains内部实现也是循环比对)都没理由比动态规划更优才对。后面我又在通过的代码里找到了一个动态规划的解法：
public static String LCS2(String str1, String str2) {
if (str1 == null || str2 == null) return "-1";
int n1 = str1.length(), n2 = str2.length();
if (n1 == 0 || n2 == 0) return "-1";
int[][] dp = new int[n1 + 1][n2 + 1];
int maxLen = 0, x = 0;
for (int i = 1; i <= n1; i++) {
char ch1 = str1.charAt(i - 1);
for (int j = 1; j <= n2; j++) {
char ch2 = str2.charAt(j - 1);
if (ch1 == ch2) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLen) {
maxLen = dp[i][j];
x = i;
}
}
}
}
return maxLen == 0 ? "-1" : str1.substring(x - maxLen, x);
} 这里dp的索引是从1开始，0位是防止数组越界，并且也有实际意义，可以理解为空子串，结果自然也是0
还有几个优化的点
- 最大公共子串的出现，必然发生在有字符相等的时候。这个应该很好理解，所以算法里只关心出现这个情况的
dp值，但是同时需要注意，此时dp里记录的值不再是连续的值了，不能再认为dp[i][j]描述的是str1中从0~i与str2中从0~j的最大公共子串，此时的dp记录值有点类似滑动窗口了，某一段时间内是持续增长的，所以他用maxLen来记录出现的最大值 - 几个临时变量存储。首先是
maxLen和x，这两个变量描述了一个子串，当出现更大的字串时更新这两个值；还有ch1和ch2，也有一定性能优化
从上面的分析可以发现，效率优化了，但是理解变困难了，最后我本地统计执行效率如下：
1AB2345CD 12345EF 我的动态规划结果：2345 LCS cost time:233600 滑动窗口结果：2345 LCS1 cost time:61400 大神的动态规划结果：2345 LCS2 cost time:42800
最后附上完整的代码：
package com.example.myapplication;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class Test {
/**
* 1AB2345CD
* 12345EF
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String str1 = sc.nextLine();
String str2 = sc.nextLine();
long startTime = System.nanoTime();
String r = LCS(str1, str2);
System.out.println(r);
System.out.println("LCS cost time:" + (System.nanoTime() - startTime));
startTime = System.nanoTime();
r = LCS1(str1, str2);
System.out.println(r);
System.out.println("LCS1 cost time:" + (System.nanoTime() - startTime));
startTime = System.nanoTime();
r = LCS2(str1, str2);
System.out.println(r);
System.out.println("LCS2 cost time:" + (System.nanoTime() - startTime));
}
sc.close();
}
/**
* longest common substring
* 动态规划算法
* dp[i][j]有两个分支
* 1. str1[i] = str2[j] dp[i][j] = dp[i][j] + 1
* 2. str1[i] != str2[j] dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
*
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
public static String LCS(String str1, String str2) {
// write code here
//零界值判断
if (str1 == null || str2 == null || (str1.isEmpty() && str2.isEmpty())) {
return "-1";
}
char[] chars1 = str1.toCharArray();
char[] chars2 = str2.toCharArray();
int str1L = chars1.length;
int str2L = chars2.length;
//动态规划结果
int[][] dp = new int[str1L][str2L];
Map<Integer, String> resultMap = new HashMap<>(str1L * (str1L - 1) + str2L - 1);
//动态规划算法
for (int i = 0; i < str1L; i++) {
for (int j = 0; j < str2L; j++) {
if (chars1[i] == chars2[j]) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
resultMap.put(i * str1L + j, "" + chars1[i]);
} else {
dp[i][j] = dp[i - 1][j - 1] + 1;
resultMap.put(i * str1L + j, resultMap.get((i - 1) * str1L + j - 1) + chars1[i]);
}
} else {
if (i == 0 || j == 0) {
dp[i][j] = 0;
resultMap.put(i * str1L + j, "");
} else {
if (dp[i][j - 1] > dp[i - 1][j]) {
dp[i][j] = dp[i][j - 1];
resultMap.put(i * str1L + j, resultMap.get(i * str1L + j - 1));
} else {
dp[i][j] = dp[i - 1][j];
resultMap.put(i * str1L + j, resultMap.get((i - 1) * str1L + j));
}
}
}
}
}
return resultMap.get(str1L * (str1L - 1) + str2L - 1);
}
/**
* 滑动窗口算法
*
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
public static String LCS1(String str1, String str2) {
// write code here
StringBuilder sb = new StringBuilder();
int start = 0, end = 1;
while (end < str1.length() + 1) {
if (str2.contains(str1.substring(start, end))) {
if (sb.length() < end - start) {
sb.delete(0, sb.length());
sb.append(str1, start, end);
}
} else {
//这个算法我曾经疑惑，假如出现start>end，程序不是会crash么
//通过debug发现，当start==end时，substring获取的是""，此时contains必然为true
//所以当start == end时，必然会走end++分支
start++;
}
end++;
}
if (sb.length() == 0) {
return "-1";
}
return sb.toString();
}
public static String LCS2(String str1, String str2) {
if (str1 == null || str2 == null) return "-1";
int n1 = str1.length(), n2 = str2.length();
if (n1 == 0 || n2 == 0) return "-1";
int[][] dp = new int[n1 + 1][n2 + 1];
int maxLen = 0, x = 0;
for (int i = 1; i <= n1; i++) {
char ch1 = str1.charAt(i - 1);
for (int j = 1; j <= n2; j++) {
char ch2 = str2.charAt(j - 1);
if (ch1 == ch2) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLen) {
maxLen = dp[i][j];
x = i;
}
}
}
}
return maxLen == 0 ? "-1" : str1.substring(x - maxLen, x);
}
} 
京公网安备 11010502036488号