1 min read
https://practice.geeksforgeeks.org/problems/longest-common-subsequence/0
Iterative
class Solution {
int dp[1005][1005];
public:
int lcs(int x, int y, string s1, string s2) {
for (int i = 0; i <= x; i++) {
for (int j = 0; j <= y; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[x][y];
}
};
Recursive
class Solution {
int dp[1005][1005];
public:
int solve(int x, int y, string s, string s2) {
if (x == 0 || y == 0) {
return dp[x][y] = 0;
} else if (dp[x][y] != -1) {
return dp[x][y];
} else {
if (s1[x - 1] == s2[y - 1]) {
return 1 + lcs(x - 1, y - 1, s1, s2);
} else {
return max(lcs(x - 1, y, s1, s2), lcs(x, y - 1, s1, s2));
}
}
}
int lcs(int x, int y, string s1, string s2) {
memset(dp, -1, sizeof(dp));
return dp[x][y];
}
}