LCS problem in python


  • 0
    F
        def lcs(self, s1, s2):
            m, n = len(s1), len(s2)
            dp = [[0] * (n + 1) for _ in range(m + 1)]
            for i in range(m):
                for j in range(n):
                    if s1[i] == s2[j]:
                        dp[i + 1][j + 1] = dp[i][j] + 1
                    else:
                        dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
            return dp[m][n]
    
        def minDistance(self, word1, word2):
            """
            :type word1: str
            :type word2: str
            :rtype: int
            """
            return len(word1) + len(word2) - 2 * self.lcs(word1, word2)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.