Amazon
Microsoft
Tencent
2020-05-25
1143. Longest Common Subsequence
Similar Question: LeetCode Question 1035, LeetCode Question 1458
Question:
Given two strings text1 and text2, return the length of their longest common subsequence.
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. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.
If there is no common subsequence, return 0.
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.
Constraints:
1 <= text1.length <= 10001 <= text2.length <= 1000- The input strings consist of lowercase English characters only.
Solution:
Similar to LeetCode Question 1035 and LeetCode Question 1458, we are using DP to record the maximum of common subsequence of current position of i, j. So if the character in i, j are not matched, dp function is dp[i][j] = Max(dp[i-1][j], dp[i][j-1]). Otherwise, it will be dp[i][j] = dp[i-1][j-1] + 1.
Time: O(nm) Space: O(nm)
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
int[][] dp = new int[n + 1][m + 1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
}
}
It could also be solved with Time: O(n*m) Space: Min(O(n), O(m)) by using a rolling dp array.
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
// To save memory by creating the array with smallest length
if (m > n) return longestCommonSubsequence(text2, text1);
int[][] dp = new int[2][m+1];
for (int i = 0; i < n; i++) {
int index = (i + 1) % 2;
for (int j = 0; j < m; j++) {
if (text1.charAt(i) == text2.charAt(j)) {
dp[index][j + 1] = dp[i % 2][j] + 1;
} else {
dp[index][j + 1] = Math.max(dp[index][j], dp[i % 2][j + 1]);
}
}
}
return dp[n % 2][m];
}
}
Follow Up question for this Problem:
- Find/Print any Longest Common Subsequence
- Find/Print all Longest Common Subsequence
Both question will need to borrow the dp array from solution 1.
1. Find/Print any Longest Common Subsequence
public String getAnyLCS(String text1, String text2, int[][] dp) {
StringBuilder sb = new StringBuilder();
int i = text1.length(), j = text2.length();
while (i > 0 && j > 0) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
sb.append(text1.charAt(i - 1));
i--;
j--;
} else if (dp[i - 1][j] >= dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return sb.reverse().toString();
}
2. Find/Print all Longest Common Subsequence
public Set<String> getAllLCS(String text1, String text2, int[][] dp) {
Set<String> results = new HashSet<>();
dfs("", text1.length(), text2.length(), text1, text2, dp, results);
return results;
}
private void dfs(String s, int i, int j, String text1, String text2, int[][] dp, Set<String> results) {
if (i == 0 || j == 0) {
results.add(new StringBuilder(s).reverse().toString());
return;
}
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dfs(s + text1.charAt(i - 1), i - 1, j - 1, text1, text2, dp, results);
} else {
if (dp[i - 1][j] >= dp[i][j - 1]) {
dfs(s, i - 1, j, text1, text2, dp, results);
}
if (dp[i][j - 1] >= dp[i - 1][j]) {
dfs(s, i, j - 1, text1, text2, dp, results);
}
}
}