Leetcode 1143. Longest Common Subsequence

Problem

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, “ace” is a subsequence of “abcde”.

A common subsequence of two strings is a subsequence that is common to both strings.

Algorithm

Dynamic Programming (DP). Define state f(i, j) is the common subsequence of text1[0…i] and text2[0…j], so we have
$$f(i,j)=\{\begin{array}{ll}f(i-1,j-1)+1& \text{if }s[left]==s[right]\\ \max [f(i-1,j),f(i,j-1)]& \text{otherwise}\end{array}$$

Code

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        slen1 = len(text1)
        slen2 = len(text2)
        if not slen1 or not slen2:
            return 0
        
        dp = [[0] * (slen2 + 1) for i in range(slen1 + 1)]
        for i in range(1, slen1 + 1):
            for j in range(1, slen2 + 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[slen1][slen2]