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.
Examples
Input: text1 = "abcde", text2 = "ace" Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is "abc" and its length is 3.
Input: text1 = "abc", text2 = "def" Output: 0 Explanation: There is no such common subsequence, so the result is 0.
Constraints
1 <= text1.length, text2.length <= 1000 text1 and text2 consist of only lowercase English characters.
Java Solution
Memoization (Top-down dynammic programming)
class Solution {
private int[][] memo;
private String text1;
private String text2;
public int longestCommonSubsequence(String text1, String text2) {
this.memo = new int[text1.length() + 1][text2.length() + 1];
for (int i = 0; i < text1.length(); i++) {
for (int j = 0; j < text2.length(); j++) {
this.memo[i][j] = -1;
}
}
this.text1 = text1;
this.text2 = text2;
return memoSolve(0, 0);
}
private int memoSolve(int p1, int p2) {
if (memo[p1][p2] != -1) {
return memo[p1][p2];
}
int answer = 0;
if (text1.charAt(p1) == text2.charAt(p2)) {
answer = 1 + memoSolve(p1 + 1, p2 + 1);
} else {
answer = Math.max(memoSolve(p1, p2 + 1), memoSolve(p1 + 1, p2));
}
memo[p1][p2] = answer;
return memo[p1][p2];
}
}
Tabulation (Bottom up dynammic programming)
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int[][] dpGrid = new int[text1.length() + 1][text2.length() + 1];
for (int col = text2.length() - 1; col >= 0; col--) {
for (int row = text1.length() - 1; row >= 0; row--) {
if (text1.charAt(row) == text2.charAt(col)) {
dpGrid[row][col] = 1 + dpGrid[row + 1][col + 1];
} else {
dpGrid[row][col] = Math.max(dpGrid[row + 1][col], dpGrid[row][col + 1]);
}
}
}
return dpGrid[0][0];
}
}