-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLongestConSub.java
More file actions
111 lines (97 loc) · 2.76 KB
/
Copy pathLongestConSub.java
File metadata and controls
111 lines (97 loc) · 2.76 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
package DP;
import org.junit.Test;
import java.util.Arrays;
/**
* @author dekai.kong
* @difficult Medium
* @create 2020-07-25 13:00
* @from
**/
public class LongestConSub {
public LongestConSub() {
}
/**
* 求最长公共子序列
* m = ABCBDAB
* n = BDCABA
* v = BCBA
* 最长公共子序列就是去掉一些字符后 不要求连续的最长子序列
* @return
* 先求长度
*/
public int longestConSubLen(String m,String n){
int mlen = m.length()+1;
int nlen = n.length()+1;
char[] mc = m.toCharArray();
char[] nc = n.toCharArray();
int[][] sublen = new int[mlen][nlen];
for (int i = 0; i < mlen; i++) {
Arrays.fill(sublen[i],0);
}
for (int i = 1; i < mlen; i++) {
for (int j = 1; j < nlen; j++) {
if(mc[i-1]==nc[j-1]){
sublen[i][j] = sublen[i-1][j-1] + 1;
}else{
sublen[i][j] = Math.max(sublen[i][j-1],sublen[i-1][j]);
}
}
}
return sublen[mlen-1][nlen-1];
}
/**
* 求最长公共子序列
* m = ABCBDAB
* n = BDCABA
* v = BCBA
* 最长公共子序列就是去掉一些字符后 不要求连续的最长子序列
* @return
* 求有哪些字母
*/
public String longestConSubString(String m,String n){
String s = "";
int mlen = m.length()+1;
int nlen = n.length()+1;
char[] mc = m.toCharArray();
char[] nc = n.toCharArray();
int[][] sublen = new int[mlen][nlen];
for (int i = 0; i < mlen; i++) {
Arrays.fill(sublen[i],0);
}
for (int i = 1; i < mlen; i++) {
for (int j = 1; j < nlen; j++) {
if(mc[i-1] == nc[j-1]){
sublen[i][j] = sublen[i-1][j-1]+1;
}else{
sublen[i][j] = Math.max(sublen[i-1][j],sublen[i][j-1]);
}
}
}
for (int i = 0; i < mlen; i++) {
for (int j = 0; j < nlen; j++) {
System.out.print(sublen[i][j]+" ");
}
System.out.println("");
}
int i = mlen-1;
int j = nlen-1;
while(sublen[i][j]>0){
//向上匹配
if(sublen[i][j] == sublen[i-1][j]){
i--;
}else if(sublen[i][j] == sublen[i][j-1]){
j--;
}else{
i--;
j--;
s = nc[j]+s;
}
}
return s;
}
@Test
public void test() {
// System.out.println(longestConSubLen("ABCBDAB","BDCABA"));
System.out.println(longestConSubString("ABCBDAB","BDCABA"));
}
}