1143. Longest Common Subsequence

[fockspaces]

take abcde v.s ace for example

1. if e match (abcde, ace), then we only need to look for abcd and ac for the following search
2. and we continue to look up the last char, (abcd, ac) not match
3. either search for (abc, ac) case or (abcd, a)
4. great! we know that we can divide the problem into sub-problems, each sub-problem state is transfered by parent

if we write as dp in 2D, we will see the path-like pattern, dp[i][j] = k means text1 i th element to last has at most k matches text2 j th element to last

for example, dp[1][2] = 2 means (cde, ce) has at least two match subsequence

	a	b	c	d	e
a	3	2	2	1	1	1
c	2	2	2	1	1	1
e	1	1	1	1	1	1

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for row in list(range(m))[::-1]:
            for col in list(range(n))[::-1]:
                match = text1[row] == text2[col]
                if match:
                    dp[row][col] = dp[row + 1][col + 1] + 1
                else:
                    dp[row][col] = max(dp[row + 1][col], dp[row][ col + 1])
        print(dp)
        return dp[0][0]

[fockspaces]

of course we can traverse from top_left to buttom_right from previous solution, we just want to match the index and preserve the last elements for default value 0

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0 for _ in range(n)] for _ in range(m)]
        for row in list(range(m)):
            for col in list(range(n)):                    
                top_left = dp[row - 1][col - 1] \
                    if row > 0 and col > 0 else 0
                top = dp[row - 1][col] if row > 0 else 0
                left = dp[row][col - 1] if col > 0 else 0
                if text1[row] == text2[col]:
                    dp[row][col] = top_left + 1
                else:
                    dp[row][col] = max(top, left)
        return dp[-1][-1]