AC Python 212 ms DP solution, O(mn) time O(n) space

  • 4

    This is similar to the longest common subsequence problem. Dynamic programming is intuitive.

    def minDistance(self, word1, word2):
        if len(word1) == 0 or len(word2) == 0:
            return max(len(word1), len(word2))
        dist = range(len(word2) + 1)
        for i in xrange(len(word1)):
            dist_ij, dist[0] = i, i + 1
            for j in xrange(len(word2)):
                if word1[i] == word2[j]:
                    dist_ij, dist[j + 1] = dist[j + 1], dist_ij
                    dist_ij, dist[j + 1] = dist[j + 1], min(dist[j], dist[j + 1], dist_ij) + 1
        return dist[-1]
    # 1146 / 1146 test cases passed.
    # Status: Accepted
    # Runtime: 212 ms
    # 96.23%

    The relations of DP are

    # keep the last char:      dist(i + 1, j + 1) = dist(i, j)
    # insert the last char:    dist(i + 1, j + 1) = dist(i + 1, j) + 1
    # replace the last char:   dist(i + 1, j + 1) = dist(i, j)     + 1
    # remove the last char:    dist(i + 1, j + 1) = dist(i, j + 1) + 1

  • 1

    This is better than my solution which uses a 3-way min comparison each time. This algorithm saves time when word1[i]==word2[j] by directly matching the latest letters. I will attempt to elaborate the reasoning as following, as a reinforcement for myself (better if it actually helps someone else: ):

    When word1[i]==word2[j], let's say, the letter is m, if in the best alignment of [i,j], word1[i] does not align with word2[j], that is, alignment[ij]==alignment[i][j-1]+1 or alignment[i-1][j]+1,let's see what happens.

    Since word1[i] and word2[j] are both m, and word1[i] does not align with word2[j], then before word2[j] comes into play, the m of word[i] must have aligned with some other m in word2. Why is this the case? Suppose if it is not the case, that is, word1[i] is not aligned with a m in word2, before word2[j] comes in, then, it would mean that, word1[i] is free to marry with word2[j] at no cost, since it is the last letter at this stage, that would make the alignment of word1[:i], word2[:j] identical to word1[:i], word2[:j-1], which is certainly better than the match of [i,j-1]+1. Well, now, we know that word1[i] is aligned with some m in word2 before word2[j]. Well, since that would mean that, if word1[i] does not align with word2[j], then all letters after that earlier m in word2 would be insertions. In this case, if we re-marry word1[i] to word2[j], nothing would change in alignment score. So, we have proved that we can always make the score better than alignment[i,j-1]+1, let's take care of the case of alignment[i-1, j]+1. But wait, we are dealing with a symmetric problem, word1 and word2 are

    symmetric in playing the rules, and the analysis is necessarily identical for the case of alignment[i-1, j] and alignment[i, j-1] when compared to alignment[i,j]. The fact that we are working in growing word2 first or word1 first does not affect the analysis since we are not relying on it. So, we have proved that when word1[i]==word2[j], then if we marry the two, the alignment score will be at least as good as alignment[i-1, j] and alignment[i, j-1], which is certainly better than either of them plus 1. So, we do not have to consider the plus one cases, but just need to directly jump to alignment[i-1][j-1].

Log in to reply

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