1143. Longest Common Subsequence (Medium)
https://leetcode.com/problems/longest-common-subsequence/
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 <= 1000
1 <= text2.length <= 1000
- The input strings consist of lowercase English characters only.
Solutions
1.
class Solution {
// This problem reminds me another problem longest consecutive common subsequence. The idea is similar that both
// employ dynamic programming. Here, I will implement the solution for longest consecutive common subsequence.
private int longestConsecutiveCommonSubsequence(String text1, String text2) {
int ans = 0;
if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) {
return ans;
}
int len1 = text1.length();
int len2 = text2.length();
// subject to text1.length() < text2.length()
// row represents the length of text2, col represents the length of text1
// initially, values for every cell is 0 by default.
int[][] dp = new int[len2 + 1][len1 + 1];
for (int i = 1; i <= len2; i++) {
for (int j = 1; j <= len1; j++) {
if (text1.charAt(j - 1) == text2.charAt(i - 1)) {
// text1 and text2 both move forward one step
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = 0;
}
ans = Math.max(ans, dp[i][j]);
}
}
return ans;
}
public int longestCommonSubsequence(String text1, String text2) {
if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) {
return 0;
}
int len1 = text1.length();
int len2 = text2.length();
// row represents the length of text1, col represents the length of text2
// initially, values for every cell is 0 by default.
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
// text1 and text2 both move forward one step
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[len1][len2];
}
private int max(int x, int y, int z) {
int tmp = Math.max(x, y);
return Math.max(tmp, z);
}
}
2.
class Solution2 {
// Inspired by https://leetcode.com/problems/longest-common-subsequence/discuss/349150/Simple-DP-in-Python-O(mn)-time-O(n)-memory-explained
// This solution saved more memory space. But a little different from the original one because we did not strictly
// make the text1 and text2 subject to text1.length > text2.length.
public int longestCommonSubsequence(String text1, String text2) {
if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) {
return 0;
}
int len1 = text1.length();
int len2 = text2.length();
// dp[curP][j] only consider the results of dp[curP-1][j], dp[curP-1][j-1] and dp[curP][j-1].
// results of dp[curP-2][*] will never be used later.
// So we can simplify the curP as current, curP-1 as previous, thus we only have to allocate
// int[2][len1+1] space and that will be enough.
int[][] dp = new int[2][len2 + 1];
for (int i = 1; i <= len1; i++) {
// parity
int prevP = (i - 1) % 2;
int curP = i % 2;
dp[curP][0] = 0;
for (int j = 1; j <= len2; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
// text1 and text2 both move forward one step
dp[curP][j] = dp[prevP][j - 1] + 1;
} else {
dp[curP][j] = max(dp[prevP][j - 1], dp[prevP][j], dp[curP][j - 1]);
}
}
}
return dp[len1 % 2][len2];
}
private int max(int x, int y, int z) {
int tmp = Math.max(x, y);
return Math.max(tmp, z);
}
}