题目描述
给两个字符串，找出最长公共子字符串
思路
DP。
给定字符串s1，s2，长度分别为m和n。
如果s2的某个字符与s1匹配，那么当前位置最长公公字符串为：前一个字符处与s1匹配的字符个数+1
如果dp[i][j]表示s1到第i个字符和s2到第j个字符已经匹配的字符个数，那么当dp[i+1][j+1]匹配时，
递推公式：dp[i+1][j+1]=dp[i][j]+1
其实只需要一维数组，因为每次取到s2的某个字符，匹配时，只需要找出前一个字符已经匹配的字符个数+1。
代码
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
| public class Main {
public static void main(String[] args){
System.out.println(new Main().getLCS("abcefedge", "fbcefed"));
}
public String getLCS(String s1, String s2) {
int n = s1.length();
int[] dp = new int[n+1];
int max = 0;
int endIndex = 0;
for(int i = 0; i < s2.length(); i++) { // i为s2当前字符的下标
char c = s2.charAt(i);
for(int j = s1.length(); j >= 1; j--) {
if(s1.charAt(j-1) == c) { // j-1为s1当前字符的下标
dp[j] = dp[j-1] + 1;
if(dp[j] > max) {
max = dp[j]; // 公共字符串的长度
endIndex = i; // 公公字符串尾字符在s2字符串的下标
}
}
}
}
if(max == 0) {
return null;
}else {
String string = s2.substring(endIndex-max+1, endIndex+1);
return string;
}
}
}
|
考察点