Here an implementation of the bottom up approach:
def longest_common_subsequence(word1: str, word2: str) → int:
dp = [[0]*(len(word1)+1) for _ in range(len(word2)+1)]
for i in range(1, len(word2)+1):
for j in range(1, len(word1)+1):
if word2[i-1] == word1[j-1]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]
That solution is incomprehensible. I have no idea what it is trying to do. Maybe Leetcode will have a better explanation.
hey, we are reworking the DP section. will have better explanation soon.
but the basic idea is to try all choices: match, skip letter in word1, skip letter in word2 and the rest is the same as dfs on tree
All Python solutions including top-down recursion, memoiation, bottom-up tabulation and space optimization, I hope this can help you understand the path of algorithm improvement
# # S1 - Top-down recursion, TC = (2**M) * (2**N), SC = M + N, LTE
# class Solution:
# def longestCommonSubsequence(self, text1: str, text2: str) -> int:
# def f(i, j, s1, s2):
# if i < 0 or j < 0:
# return 0
# if s1[i] != s2[j]:
# return max(f(i-1, j, s1, s2), f(i, j-1, s1, s2))
# else:
# # Take
# take = 1 + f(i-1, j-1, s1, s2)
# not_take = max(f(i-1, j, s1, s2), f(i, j-1, s1, s2))
# return max(take, not_take)
# m, n = len(text1), len(text2)
# return f(m-1, n-1, text1, text2)
# # S2 - Top-down recursion with memoiation, TC = M*N, SC = M + N + MN
# class Solution:
# def longestCommonSubsequence(self, text1: str, text2: str) -> int:
# def f(i, j, s1, s2, dp):
# if i < 0 or j < 0:
# return 0
# if dp[i][j] != -1:
# return dp[i][j]
# if s1[i] != s2[j]:
# dp[i][j] = max(f(i-1, j, s1, s2, dp), f(i, j-1, s1, s2, dp))
# else:
# # Take
# take = 1 + f(i-1, j-1, s1, s2, dp)
# not_take = max(f(i-1, j, s1, s2, dp), f(i, j-1, s1, s2, dp))
# dp[i][j] = max(take, not_take)
# return dp[i][j]
# m, n = len(text1), len(text2)
# dp =[[-1 for _ in range(n)] for _ in range(m)]
# return f(m-1, n-1, text1, text2, dp)
# # S3 - Top-down recursion with memoiation, updating dp index to
# # prepare bottom-up tabulation
# class Solution:
# def longestCommonSubsequence(self, text1: str, text2: str) -> int:
# def f(i, j, s1, s2, dp):
# if i == 0 or j == 0:
# return 0
# if dp[i][j] != -1:
# return dp[i][j]
# if s1[i-1] != s2[j-1]:
# dp[i][j] = max(f(i-1, j, s1, s2, dp), f(i, j-1, s1, s2, dp))
# else:
# # Take
# take = 1 + f(i-1, j-1, s1, s2, dp)
# not_take = max(f(i-1, j, s1, s2, dp), f(i, j-1, s1, s2, dp))
# dp[i][j] = max(take, not_take)
# return dp[i][j]
# m, n = len(text1), len(text2)
# dp =[[-1 for _ in range(n+1)] for _ in range(m+1)]
# return f(m, n, text1, text2, dp)
# # S4 - Bottom-up tabulation, TC = MN, SC = MN
# class Solution:
# def longestCommonSubsequence(self, s1: str, s2: str) -> int:
# m, n = len(s1), len(s2)
# dp =[[0 for _ in range(n+1)] for _ in range(m+1)]
# # Build base cases - no need here since we initialized dp to 0s already
# # For nested loop from bottom
# for i in range(1, m+1):
# for j in range(1, n+1):
# if s1[i-1] != s2[j-1]:
# dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# else:
# take = 1 + dp[i-1][j-1]
# not_take = max(dp[i-1][j], dp[i][j-1])
# dp[i][j] = max(take, not_take)
# return dp[-1][-1]
# S5 - Bottom-up tabulation with space optimization, TC = MN, SC = N
class Solution:
def longestCommonSubsequence(self, s1: str, s2: str) -> int:
m, n = len(s1), len(s2)
pre = [0 for _ in range(n+1)]
# Build base cases - no need here since we initialized dp to 0s already
# For nested loop from bottom
for i in range(1, m+1):
cur = [0 for _ in range(n+1)]
for j in range(1, n+1):
if s1[i-1] != s2[j-1]:
cur[j] = max(pre[j], cur[j-1])
else:
take = 1 + pre[j-1]
not_take = max(pre[j], cur[j-1])
cur[j] = max(take, not_take)
pre = cur
return pre[-1]
def longest_common_subsequence(word1: str, word2: str) -> int:
# WRITE YOUR BRILLIANT CODE HERE
dp = [[0 for j in range(len(word2)+1)] for i in range(len(word1)+1)]
for i in range(len(word1)-1, -1, -1):
for j in range(len(word2)-1, -1, -1):
if word1[i] == word2[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]
if __name__ == '__main__':
word1 = input()
word2 = input()
res = longest_common_subsequence(word1, word2)
print(res)
nice work!
but the last solution (S5) does not optimze for space as you create “cur = [0 for _ in range(n+1)]” m times potentially using O(MN) space if the garbage collector does not kick in in the meantime
Hi, can someone explain me why some times on the illustration of some solution we start from the beginning of string for example , but in the implementation it is always from the end of the string .
function longestCommonSubsequence(word1, word2) {
11 let n = word1.length;
12 let m = word2.length;
13 return lcs(n, m, word1, word2);
and on illustration we compare first symbols with index 0 and 0.
Thank you.