[Python] DP Longest Common Subsequence


  • 0
    P
    class Solution(object):
        def minDistance(self, word1, word2):
            """
            :type word1: str
            :type word2: str
            :rtype: int
            """
            ## Longest Common Subsequence
            ## dp[i][j] = 0, if len(word1) == 0 or len(word2)==0
            ##          = dp[i-1][j-1]+1, if word1[i] == word2[j]
            ##          = max(dp[i-1][j], dp[i][j-1])
            dp = [[0 for col in range(len(word2)+1)] for row in range(len(word1)+1)]
            for i in range(len(word1)):
                for j in range(len(word2)):
                    if word1[i] == word2[j]:
                        ## row=i+1, col=j+1
                        dp[i+1][j+1] = dp[i+1-1][j+1-1] + 1
                    else:
                        dp[i+1][j+1] = max(dp[i+1-1][j+1], dp[i+1][j+1-1])                    
            lcs_seq = dp[len(word1)][len(word2)]
    
    
            return(len(word1)-lcs_seq + len(word2)-lcs_seq)
    

    MindMap: Two strings become same one => Longest Common Subsequence or Substring.

    (Note: these are 2 slightly different problems)

    Because I realized deleting character can be arbitrary after failing one of the tests ("park" and "spake"), longest common subsequence is the direction I should follow.


Log in to reply
 

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