Dare2Solve
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".
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.
Define the DP Array:
dp[i][j]
represents the length of the LCS of text1[0:i]
and text2[0:j]
.Base Cases:
dp[0][j]
and dp[i][0]
to 0 for all i
and j
.State Transition:
text1[i-1]
and text2[j-1]
are the same, then dp[i][j] = dp[i-1][j-1] + 1
.dp[i][j] = max(dp[i-1][j], dp[i][j-1])
.Result:
text1
and text2
will be dp[len(text1)][len(text2)]
.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
.
O(m * n)
for the DP array. However, this can be optimized to O(min(m, n))
by using a rolling array technique.
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
unordered_map<string, int> memoMap;
return lcs(text1, text2, 0, 0, memoMap);
}
private:
int lcs(const string& text1, const string& text2, int i, int j, unordered_map<string, int>& 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;
}
};
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)
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
Map<String, Integer> memoMap = new HashMap<>();
return lcs(text1, text2, 0, 0, memoMap);
}
private int lcs(String text1, String text2, int i, int j, Map<String, Integer> 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;
}
}
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);
};