1143. Longest Common Subsequence

Medium

Given two strings text1 and text2, return the length of their longest common subsequence. 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. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings. If there is no common subsequence, return 0.

Solution

O(mn)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        n,m=len(text1),len(text2)
        dp=[[0]*(m+1) for _ in range(n+1)]
        
        for i, t1 in enumerate(text1):
            for j, t2 in enumerate(text2):
                if t1 == t2:
                    dp[i+1][j+1] = 1 + dp[i][j]
                else:
                    dp[i+1][j+1] = max(dp[i+1][j] , dp[i][j+1])
    
        return dp[-1][-1]