Longest Common Subsequence — 2D DP Preview
Sanjeev SharmaAdvertisement
Problem
Find the length of the longest common subsequence of strings text1 and text2.
Example: text1="abcde", text2="ace" → 3
Approach — 2D DP (previewed here, detailed in 2D DP section)
dp[i][j] = LCS of text1[:i] and text2[:j].
text1[i-1]==text2[j-1]:dp[i][j] = dp[i-1][j-1] + 1- else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Time: O(mn) | Space: O(mn), optimizable to O(n)
Solutions
Python
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m,n=len(text1),len(text2)
dp=[[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if text1[i-1]==text2[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
return dp[m][n]
Python — Space Optimized
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m,n=len(text1),len(text2)
prev=[0]*(n+1)
for i in range(1,m+1):
curr=[0]*(n+1)
for j in range(1,n+1):
if text1[i-1]==text2[j-1]: curr[j]=prev[j-1]+1
else: curr[j]=max(prev[j],curr[j-1])
prev=curr
return prev[n]
Complexity
- Time: O(m*n) | Space: O(n) with space optimization
Advertisement
