-
Notifications
You must be signed in to change notification settings - Fork 0
/
printLCS.java
109 lines (93 loc) · 2.93 KB
/
printLCS.java
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
class Solution{
static void lcs(String s1, String s2) {
int n=s1.length();
int m=s2.length();
int dp[][]=new int[n+1][m+1];
for(int i=0;i<=n;i++){
dp[i][0] = 0;
}
for(int i=0;i<=m;i++){
dp[0][i] = 0;
}
for(int ind1=1;ind1<=n;ind1++){
for(int ind2=1;ind2<=m;ind2++){
if(s1.charAt(ind1-1)==s2.charAt(ind2-1))
dp[ind1][ind2] = 1 + dp[ind1-1][ind2-1];
else
dp[ind1][ind2] = 0 + Math.max(dp[ind1-1][ind2],dp[ind1][ind2-1]);
}
}
int len=dp[n][m];
int i=n;
int j=m;
int index = len-1;
String str="";
for(int k=1; k<=len;k++){
str +="$"; // dummy string
}
StringBuilder ss= new StringBuilder(s1);
StringBuilder str2=new StringBuilder(str);
while(i>0 && j>0){
if(ss.charAt(i-1) == s2.charAt(j-1)){
str2.setCharAt(index,ss.charAt(i-1) );
index--;
i--;
j--;
}
else if(ss.charAt(i-1)>s2.charAt(j-1)){
i--;
}
else j--;
}
System.out.println(str2);
}
public static void main(String args[]) {
String s1= "abcde";
String s2= "bdgek";
System.out.print("The Longest Common Subsequence is ");
lcs(s1,s2);
}
}
//Corrected Code fot the printing the LCS
public class Main {
public static void main(String[] args) {
lcs("raushan", "reetsh");
}
static void lcs(String s1, String s2) {
int n = s1.length();
int m = s2.length();
int dp[][] = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int i = 0; i <= m; i++) {
dp[0][i] = 0;
}
for (int ind1 = 1; ind1 <= n; ind1++) {
for (int ind2 = 1; ind2 <= m; ind2++) {
if (s1.charAt(ind1 - 1) == s2.charAt(ind2 - 1))
dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1];
else
dp[ind1][ind2] = Math.max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]);
}
}
int len = dp[n][m];
int i = n;
int j = m;
int index = len - 1;
char[] strArray = new char[len]; // Use char array instead of StringBuilder
while (i > 0 && j > 0) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
strArray[index] = s1.charAt(i - 1);
index--;
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
System.out.println(new String(strArray)); // Convert char array to String for printing
}
}