edit_distance

View Source

 1from functools import cache
 2
 3
 4# @leet start
 5class Solution:
 6    def minDistance(self, word1: str, word2: str) -> int:
 7        """
 8        This question asks us to find the edit distance of two strings, or the amount
 9        of insert, update, and delete operations to transform word1 to word2.
10
11        So, we have a few cases:
12
13        1. if l == r, then we know their edit distance is 0.
14        2. If l is empty, we know the edit distance is the length of r
15        3. If r is empty, we know the edit distance is the length of l
16        4. If l[0] == r[0], we can increment our pointer
17        5. Insertion increments the right pointer
18        6. Updating increments both pointers
19        7. Deletion increments the left pointer
20
21        If we do an operation, we have to return 1 + the operation, but we always
22        want the minimum cost, so we return the cost of the operation that
23        results in the fewest operations
24
25        This runs in $O(m * n)$ time.
26        """
27
28        @cache
29        def dp(l, r):
30            if l == r:
31                return 0
32            if not l:
33                return len(r)
34            if not r:
35                return len(l)
36            if l[0] == r[0]:
37                return dp(l[1:], r[1:])
38            insert = dp(l, r[1:])
39            update = dp(l[1:], r[1:])
40            delete = dp(l[1:], r)
41            return 1 + min(insert, update, delete)
42
43        return dp(word1, word2)
44
45
46# @leet end
47
48
49def test():
50    assert 2 + 2 == 4

class Solution: View Source

 6class Solution:
 7    def minDistance(self, word1: str, word2: str) -> int:
 8        """
 9        This question asks us to find the edit distance of two strings, or the amount
10        of insert, update, and delete operations to transform word1 to word2.
11
12        So, we have a few cases:
13
14        1. if l == r, then we know their edit distance is 0.
15        2. If l is empty, we know the edit distance is the length of r
16        3. If r is empty, we know the edit distance is the length of l
17        4. If l[0] == r[0], we can increment our pointer
18        5. Insertion increments the right pointer
19        6. Updating increments both pointers
20        7. Deletion increments the left pointer
21
22        If we do an operation, we have to return 1 + the operation, but we always
23        want the minimum cost, so we return the cost of the operation that
24        results in the fewest operations
25
26        This runs in $O(m * n)$ time.
27        """
28
29        @cache
30        def dp(l, r):
31            if l == r:
32                return 0
33            if not l:
34                return len(r)
35            if not r:
36                return len(l)
37            if l[0] == r[0]:
38                return dp(l[1:], r[1:])
39            insert = dp(l, r[1:])
40            update = dp(l[1:], r[1:])
41            delete = dp(l[1:], r)
42            return 1 + min(insert, update, delete)
43
44        return dp(word1, word2)

def minDistance(self, word1: str, word2: str) -> int: View Source

 7    def minDistance(self, word1: str, word2: str) -> int:
 8        """
 9        This question asks us to find the edit distance of two strings, or the amount
10        of insert, update, and delete operations to transform word1 to word2.
11
12        So, we have a few cases:
13
14        1. if l == r, then we know their edit distance is 0.
15        2. If l is empty, we know the edit distance is the length of r
16        3. If r is empty, we know the edit distance is the length of l
17        4. If l[0] == r[0], we can increment our pointer
18        5. Insertion increments the right pointer
19        6. Updating increments both pointers
20        7. Deletion increments the left pointer
21
22        If we do an operation, we have to return 1 + the operation, but we always
23        want the minimum cost, so we return the cost of the operation that
24        results in the fewest operations
25
26        This runs in $O(m * n)$ time.
27        """
28
29        @cache
30        def dp(l, r):
31            if l == r:
32                return 0
33            if not l:
34                return len(r)
35            if not r:
36                return len(l)
37            if l[0] == r[0]:
38                return dp(l[1:], r[1:])
39            insert = dp(l, r[1:])
40            update = dp(l[1:], r[1:])
41            delete = dp(l[1:], r)
42            return 1 + min(insert, update, delete)
43
44        return dp(word1, word2)

This question asks us to find the edit distance of two strings, or the amount of insert, update, and delete operations to transform word1 to word2.

So, we have a few cases:

if l == r, then we know their edit distance is 0.
If l is empty, we know the edit distance is the length of r
If r is empty, we know the edit distance is the length of l
If l[0] == r[0], we can increment our pointer
Insertion increments the right pointer
Updating increments both pointers
Deletion increments the left pointer

If we do an operation, we have to return 1 + the operation, but we always want the minimum cost, so we return the cost of the operation that results in the fewest operations

This runs in $O(m * n)$ time.

def test(): View Source

50def test():
51    assert 2 + 2 == 4