Algorithm Puzzles: Edit Distance

Posted on Edited on In Views: Word count in article: 151 Reading time ≈ 1 mins.

Algorithm Puzzles everyday every week sometimes: Edit Distance

Puzzle

Puzzle from leetcode:

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character
Delete a character
Replace a character

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    dp = {}
    @lru_cache
    def minDistance(self, word1: str, word2: str) -> int:
        if not word1:
            return len(word2)
        if not word2:
            return len(word1)
        if word1[0] == word2[0]:
            return self.minDistance(word1[1:], word2[1:])
        if (word1, word2) not in self.dp:
            # insert makes word1[n-1] == word2[n]
            opInsert = self.minDistance(word1, word2[1:]) + 1
            # delete makes word1[n+1] == word2[n]
            opDelete = self.minDistance(word1[1:], word2) + 1
            # replace makes word1[n] == word2[n]
            opReplace = self.minDistance(word1[1:], word2[1:]) + 1
            self.dp[(word1, word2)] = min(opInsert, opDelete, opReplace)
            
        return self.dp[(word1, word2)]

T.C. should be O(len(word1) * len(word2))