题解 | #最长公共子串#
最长公共子串
https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac
import java.util.*;
public class Solution {
/**
* longest common substring
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
public String LCS (String str1, String str2) {
// write code here
int len1= str1.length();
int len2 = str2.length();
int m=0,n=0,num=0;
int[][] dp = new int[len1+1][len2+1];
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(str1.charAt(i-1)==str2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+1;
if(num<dp[i][j]){
num=dp[i][j];
m=i;
n=j;
}
}
else
dp[i][j]=0;
}
}
StringBuffer sb =new StringBuffer();
while(dp[m][n]!=0){
sb.append(str1.charAt(m-1));
m--;
n--;
}
if(sb.length()==0)
return "-1";
return sb.reverse().toString();
}
}
查看10道真题和解析