-
Notifications
You must be signed in to change notification settings - Fork 0
/
LCS.java
150 lines (123 loc) · 4.1 KB
/
LCS.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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
// LCS
// 1143. Longest Common Subsequence
// Medium
// 10K
// 117
// Companies
// Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
// A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
// For example, "ace" is a subsequence of "abcde".
// A common subsequence of two strings is a subsequence that is common to both strings.
// Example 1:
// Input: text1 = "abcde", text2 = "ace"
// Output: 3
// Explanation: The longest common subsequence is "ace" and its length is 3.
// Example 2:
// Input: text1 = "abc", text2 = "abc"
// Output: 3
// Explanation: The longest common subsequence is "abc" and its length is 3.
// Example 3:
// Input: text1 = "abc", text2 = "def"
// Output: 0
// Explanation: There is no such common subsequence, so the result is 0.
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int dp[][]=new int[text1.length()][text2.length()];
for(int row[]:dp)
{
Arrays.fill(row,-1);
}
//return lcsRecursion(text1,text2,text1.length()-1,text2.length()-1);
// return lcsMemoization(text1,text2,text1.length()-1,text2.length()-1,dp);
// return lcsDP(text1,text2);
return lcsDPOptimized(text1,text2);
}
//Recursive Approach
public static int lcsRecursion(String text1, String text2,int ind1,int ind2)
{
if(ind1<0 || ind2<0)
{
return 0;
}
if(text1.charAt(ind1)==text2.charAt(ind2))
{
return 1+lcsRecursion(text1,text2,ind1-1,ind2-1);
}
return Math.max(lcsRecursion(text1,text2,ind1,ind2-1),lcsRecursion(text1,text2,ind1-1,ind2));
}
//Memoization Approach
public static int lcsMemoization(String text1, String text2,int ind1,int ind2,int dp[][])
{
if(ind1<0 || ind2<0)
{
return 0;
}
if(dp[ind1][ind2]!=-1)
{
return dp[ind1][ind2];
}
if(text1.charAt(ind1)==text2.charAt(ind2))
{
return 1+lcsMemoization(text1,text2,ind1-1,ind2-1,dp);
}
return dp[ind1][ind2]=Math.max(lcsMemoization(text1,text2,ind1,ind2-1,dp),lcsMemoization(text1,text2,ind1-1,ind2,dp));
}
//DP Approach
public static int lcsDP(String text1,String text2)
{
int dp[][]=new int[text1.length()+1][text2.length()+1];
int m=text1.length();
int n=text2.length();
for(int i=0;i<=m;i++)
{
dp[i][0]=0;
}
for(int i=0;i<=n;i++)
{
dp[0][i]=0;
}
for(int ind1=1;ind1<=text1.length();ind1++)
{
for(int ind2=1;ind2<=text2.length();ind2++)
{
if(text1.charAt(ind1-1)==text2.charAt(ind2-1))
{
dp[ind1][ind2]=1+dp[ind1-1][ind2-1];
}
else
{
dp[ind1][ind2]=Math.max(dp[ind1][ind2-1],dp[ind1-1][ind2]);
}
}
}
return dp[m][n];
}
//DP Approach Optimized
public static int lcsDPOptimized(String text1,String text2)
{
int dp[]=new int[text2.length()+1];
int m=text1.length();
int n=text2.length();
for(int i=0;i<=n;i++)
{
dp[i]=0;
}
for(int ind1=1;ind1<=text1.length();ind1++)
{
int curr[]=new int[n+1];
for(int ind2=1;ind2<=text2.length();ind2++)
{
if(text1.charAt(ind1-1)==text2.charAt(ind2-1))
{
curr[ind2]=1+dp[ind2-1];
}
else
{
curr[ind2]=Math.max(curr[ind2-1],dp[ind2]);
}
}
dp=curr;
}
return dp[n];
}
}