Concise and Simple Python DP


  • 0
    E

    Use dp to find the longest common subsequence between the two words, then sum up the difference in length between the LCS and each word.

        def minDistance(self, word1, word2):
    
            row = [0 for _ in range(len(word1)+1)]
            for r in range(1, len(word2)+1):
                prev = 0
                for c in range(1, len(row)):
                    val = prev+1 if word1[c-1] == word2[r-1] else max(row[c],row[c-1])
                    row[c], prev = val, row[c]
            return len(word1) + len(word2) - 2 * row[-1]
    

Log in to reply
 

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