Longest Common Subsequence | LeetCode | Solution Explained
Longest Common Subsequence. One of the most popular string DP questions. I explain the logic with recursive & iterative dynamic programming approach coded in Python3.
Problem: https://leetcode.com/problems/longest-common-subsequence/
Contents hide
Logic
- Let
sandtbe source and target sentences - These are the same as
text1andtext2 - Each character is either a part of the answer OR it is not
- Have two pointers i, j pointing to s and t respectively
- if
s[i] == t[j],- we have a match, thus its a good idea to include this character
- if not,
- we try skipping over the character in
sby doingi+1or do skip over character intby doingj+1
- we try skipping over the character in
- we don’t know which is the better case, so we spawn a recursion in both cases and store the max(case1, case2)
Recursive Solution
class Solution:
def longestCommonSubsequence(self, s: str, t: str) -> int:
@lru_cache(None)
def recurse(i, j):
if i >= m or j >= n: return 0
if s[i] == t[j]: return 1 + recurse(i+1, j+1)
return max(recurse(i+1, j), recurse(i, j+1))
m, n = len(s), len(t)
return recurse(0, 0)Iterative Solution
We can now just convert the iterative logic into recursive logic.
class Solution:
def longestCommonSubsequence(self, s: str, t: str) -> int:
m, n = len(s), len(t)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in reversed(range(m)):
for j in reversed(range(n)):
if s[i] == t[j]:
dp[i][j] = 1 + dp[i+1][j+1]
else:
dp[i][j] = max(dp[i+1][j], dp[i][j+1])
return dp[0][0]
Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Reverse integer | InterviewBit | LeetCode | Solution Explained
January 24, 2022