π Problem Details
- Title:
1143. Longest Common Subsequence
- Link: https://leetcode.com/problems/longest-common-subsequence/
- Difficulty: Medium
- Tags/Categories: Dynamic-Programming
input strings
text1
andtext2
return the length of their longest common subsequence return 0 if there is no common subsequence subsequence: new string generated from the original string with some or no characters deleted without changing the relative order of the remaining characters
πWhat Were My Initial Thoughts?
1. Can it be broken into subproblems?
- if the last characters of both strings match, they contribute to the LCS
- otherwise, we must consider the LCS by ignoring either the last character of `text1` or `text2`.
2. Choose Top-Down vs Bottom-Up
- can use either
- will go with a bottom up approach where we buld the solution from smaller substrings
3. Define DP State
- let dp[i][j] represent the length of the LCS for
- `text1[0..i-1]` and `text2[0..j-1]
- base case: if either string is empty, LCS is 0
- dp[0][j] = 0
- dp[i][0] = 0
π‘ Explanation of Solution
1. Base Case: Building the Foundation
-
imagine we are filling out a grid (DP table) where:
- rows represent
text1
(first string) - columns represent
text2
(second string) - each cell
dp[i][j]
represents the LCS length fortext1[0...i-1]
andtext2[0...j-1]
.**
- rows represent
-
Why do we set the entire first row and column to
zero
?- if either string is empty, there is no common subsequence, so the LCS is
0
- this is why we initialize:
dp[0][j] = 0
β Whentext1
is empty.dp[i][0] = 0
β Whentext2
is empty.
- if either string is empty, there is no common subsequence, so the LCS is
This gives us the following starting DP table for text1 = "abcde"
and text2 = "ace"
:
'' a c e
'' 0 0 0 0
a 0
b 0
c 0
d 0
e 0
Each 0
in the first row and first column means βno charactersβ in one of the strings, so LCS is 0
.
2. Filling the Table - How do we move?
- Case 1: Characters match
text1[i-1] == text2[j-1]
- if they match, they contribute to the LCS
- we extend the LCS from the previous diagonal cell
dp[i-1][j-1]
and add 1 - Formula:
dp[i][j] = 1 + dp[i-1][j-1]
- Case 2: Characters donβt match
text1[i-1] != text2[j-1]
- we must ignore one character from either
text1
ortext2
and take the maximum LCS possible from previous results - Formula:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]
Final Answer
at the end of filling the table, dp[m][n]
contains the length of the longest common subsequence
'' a c e
'' 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3 <-- Final answer = `dp[5][3] = 3`
β Complexity Analysis
Time Complexity: O(m * n)
Space Complexity: O(m * n)
π» Implementation of Solution
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int n = text2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
// fill dp table bottom up
for(int i=1; i <= m; i++) {
for(int j=1; j <= n; j++) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1]; // Match, extend LCS
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // Exclude one character
}
}
}
return dp[m][n];
}
};