Solution using DP in python, time: O(mn), space:O(mn)


  • 0
    E

    explanation:

    1. Regarding the problem (i,j) (i.e. comparing word1[:i+1] and word2[:j+1]) , the directly related subproblems are namely (i-1,j-1), (i,j-1),(i-1,j), each of them can be calculated within a right-down direction in a n*m matrix. This is the big picture.
    2. How to construct the solution of problem (i,j) with the solution of (i-1,j-1), (i,j-1),(i-1,j)? The allowed operations are replacing, deleting and adding one character. Thus, if the current characters under comparing (say word1[i] and word2[j] ),
      There are 2 cases:
      Case 1. if they are equal, the solution of (i,j) is the same as (i-1,j-1).
      Case 1 solution: dp[i][j]=dp[i-1][j-1]
      Case 2. if they are not equal, we can either add/delete 1 letter (both are 1 operation cost) based on solution (i-1,j),(i,j-1) or delete (1 operation) or replace word1[i] with word2[j], vice versa.
      Case 2 solution: dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i-1],[j])+1

    code:

    class Solution:
        def minDistance(self, word1, word2):
            if word1==word2:
                return 0
            m,n=len(word1)+1,len(word2)+1
            dp=[[0 for i in range(n)] for j in range(m)]
            for i in range(m):
                dp[i][0]=i
            for j in range(n):
                dp[0][j]=j
    
            for i in range(1,m):
                for j in range(1,n):
                    if word1[i-1]==word2[j-1]:
                        dp[i][j]=dp[i-1][j-1]
                    else:
                        dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1
            return dp[m-1][n-1]
    

    Any improving advice is appreciated :)


Log in to reply
 

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