forked from IvanLu1024/Java-Notes
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLCS.java
More file actions
51 lines (46 loc) · 1.08 KB
/
Copy pathLCS.java
File metadata and controls
51 lines (46 loc) · 1.08 KB
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package code_07_dp;
import org.junit.Test;
/**
* Sample Input:
abcfbc abfcab
programming contest
abcd mnp
* Sample Output:
4
2
0
*/
public class LCS {
public int LCS(String s,String t){
int m=s.length();
int n=t.length();
if(m==0 || n==0){
return 0;
}
int[][] lcs=new int[m+1][n+1];
for(int i=0;i<m+1;i++){
for(int j=0;j<n+1;j++){
lcs[i][j]=0;
}
}
for(int i=1;i<m+1;i++){
for(int j=1;j<n+1;j++){
//注意：这里的i是从1开始的 i=m时，实际上取到的是s的第m个元素
if(s.charAt(i-1)==t.charAt(j-1)){
lcs[i][j]=1+lcs[i-1][j-1];
}else{
lcs[i][j]=Math.max(lcs[i-1][j],lcs[i][j-1]);
}
}
}
return lcs[m][n];
}
@Test
public void test(){
String s="abcfbc";
String t="abfcab";
//String s="a";
//String t="ab";
System.out.println(LCS(s,t));
}
}