DP solution in Python


  • 0
    H

    This is a standard dynamic programming problem. Once you realize this feature, it is not hard at all, just be careful of different cases for the recurrence relation.

    class Solution(object):
        def minDistance(self, word1, word2):
            """
            :type word1: str
            :type word2: str
            :rtype: int
            """
            n1, n2 = len(word1), len(word2)
            # initialize a DP table, table[i][j] means the distance between words[:i] and words[:j]
            table = [[0 for j in range(n2+1)] for i in range(n1+1)]
            for j in range(1, n2+1):  table[0][j] = j
            for i in range(1, n1+1):  table[i][0] = i
            # fill the table
            for i in range(0, n1):
                for j in range(0, n2):
                    if word1[i] == word2[j]:
                        table[i+1][j+1] = min(1+table[i+1][j], 1+table[i][j+1], table[i][j])
                    else:
                        table[i+1][j+1] = min(1+table[i+1][j], 1+table[i][j+1], 1+table[i][j])
            return table[n1][n2]
    

Log in to reply
 

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