9 line AC Python with DP


  • 1
    S

    with 1D array,record the left_top

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

Log in to reply
 

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