
Description
The problem is to find the length of the longest common subsequence (LCS) between two strings, text1
and text2
. A subsequence is a sequence that appears in the same relative order but not necessarily contiguously. For example, "ace" is a subsequence of "abcde".
Intuition
The intuition behind solving this problem is to use dynamic programming (DP) to avoid redundant calculations and efficiently find the LCS. By breaking the problem into smaller subproblems and storing the results of these subproblems, we can build up the solution to the original problem.
Approach
- Define the DP Array:
- Create a 2D DP array, where
dp[i][j]
represents the length of the LCS oftext1[0:i]
andtext2[0:j]
. - Base Cases:
- If either string is empty, the LCS length is 0. Initialize
dp[0][j]
anddp[i][0]
to 0 for alli
andj
. - State Transition:
- If the characters
text1[i-1]
andtext2[j-1]
are the same, thendp[i][j] = dp[i-1][j-1] + 1
. - If the characters are different, thendp[i][j] = max(dp[i-1][j], dp[i][j-1])
. - Result:
- The length of the LCS of
text1
andtext2
will bedp[len(text1)][len(text2)]
.
Complexity
Time Complexity:
O(m * n)
, where m
is the length of text1
and n
is the length of text2
. This is because we are filling out a 2D DP array of size m * n
.
Space Complexity:
O(m * n)
for the DP array. However, this can be optimized to O(min(m, n))
by using a rolling array technique.
Code
C++
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
unordered_map memoMap;
return lcs(text1, text2, 0, 0, memoMap);
}
private:
int lcs(const string& text1, const string& text2, int i, int j, unordered_map& memoMap) {
if (i == text1.length() || j == text2.length()) return 0;
string key = to_string(i) + "," + to_string(j);
if (memoMap.find(key) != memoMap.end()) return memoMap[key];
int result;
if (text1[i] == text2[j]) {
result = 1 + lcs(text1, text2, i + 1, j + 1, memoMap);
} else {
result = max(lcs(text1, text2, i, j + 1, memoMap), lcs(text1, text2, i + 1, j, memoMap));
}
memoMap[key] = result;
return result;
}
};
Python
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
memoMap = {}
def lcs(i, j):
if i == len(text1) or j == len(text2):
return 0
key = (i, j)
if key in memoMap:
return memoMap[key]
if text1[i] == text2[j]:
result = 1 + lcs(i + 1, j + 1)
else:
result = max(lcs(i, j + 1), lcs(i + 1, j))
memoMap[key] = result
return result
return lcs(0, 0)
Java
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
Map memoMap = new HashMap<>();
return lcs(text1, text2, 0, 0, memoMap);
}
private int lcs(String text1, String text2, int i, int j, Map memoMap) {
if (i == text1.length() || j == text2.length()) return 0;
String key = i + "," + j;
if (memoMap.containsKey(key)) return memoMap.get(key);
int result;
if (text1.charAt(i) == text2.charAt(j)) {
result = 1 + lcs(text1, text2, i + 1, j + 1, memoMap);
} else {
result = Math.max(lcs(text1, text2, i, j + 1, memoMap), lcs(text1, text2, i + 1, j, memoMap));
}
memoMap.put(key, result);
return result;
}
}
JavaScript
var longestCommonSubsequence = function(text1, text2) {
let memoMap = new Map();
const lcs = (i, j) => {
if (i === text1.length || j === text2.length) return 0;
let key = `${i},${j}`;
if (memoMap.has(key)) return memoMap.get(key);
let result;
if (text1[i] === text2[j]) {
result = 1 + lcs(i + 1, j + 1);
} else {
result = Math.max(lcs(i, j + 1), lcs(i + 1, j));
}
memoMap.set(key, result);
return result;
}
return lcs(0, 0);
};