pytudes._2021.leetcode.hard._72__edit_distance

https://leetcode.com/problems/edit-distance/

Constraints:

  • 0 ≀ word1.length, word2.length ≀ 500

  • word1 and word2 consist of lowercase English letters.

Examples:
>>> Solution().minDistance("fat", "cat")
1
See Also:

Module Contents

Classes

Solution

Functions

compute_edit_distance(word1,Β word2)

Returns the Levenshtein (edit) distance between two words

compute_edit_distance_cache(word1,Β word2)

Returns the Levenshtein (edit) distance between two words
class pytudes._2021.leetcode.hard._72__edit_distance.Solution[source]
minDistance(word1, word2)[source]
Parameters:

  • word1 (str) –

  • word2 (str) –

Return type:

int

pytudes._2021.leetcode.hard._72__edit_distance.compute_edit_distance(word1, word2)[source]

Returns the Levenshtein (edit) distance between two words

The edit distance is the minimum number of operations required to convert word1 to word2.

Based on the observation that word transformation can be achieved via three distinct character operations:

  1. Insertion

  2. Deletion

  3. Substitution

Args:

word2: word1:

Examples:
>>> compute_edit_distance('','')
0
>>> compute_edit_distance("a",'')
1
>>> compute_edit_distance('',"a")
1
>>> compute_edit_distance("abc",'')
3
>>> compute_edit_distance('',"abc")
3
>>> compute_edit_distance("islander","slander")
1
>>> compute_edit_distance("mart","karma")
3
>>> compute_edit_distance("kitten","sitting")
3
>>> compute_edit_distance("ball","football")
4
>>> compute_edit_distance("football","foot")
4

>>> compute_edit_distance("horse","ros")
3
>>> # horse -> rorse (replace "h" with "r")
>>> # rorse -> rose (remove "r")
>>> # rose -> ros (remove "e")

>>> compute_edit_distance("intention","execution")
5
>>> # intention -> inention (remove "t")
>>> # inention -> enention (replace "i" with "e")
>>> # enention -> exention (replace "n" with "x")
>>> # exention -> exection (replace "n" with "c")
>>> # exection -> execution (insert "u")
Parameters:

  • word1 (str) –

  • word2 (str) –

Return type:

int

pytudes._2021.leetcode.hard._72__edit_distance.compute_edit_distance_cache(word1, word2)[source]

Returns the Levenshtein (edit) distance between two words

The edit distance is the minimum number of operations required to convert word1 to word2.

Based on the observation that word transformation can be achieved via three distinct character operations:

  1. Insertion

  2. Deletion

  3. Substitution

Args:

word2: word1:

Examples:
>>> compute_edit_distance_cache('','')
0
>>> compute_edit_distance_cache("a",'')
1
>>> compute_edit_distance_cache('',"a")
1
>>> compute_edit_distance_cache("abc",'')
3
>>> compute_edit_distance_cache('',"abc")
3
>>> compute_edit_distance_cache("islander","slander")
1
>>> compute_edit_distance_cache("mart","karma")
3
>>> compute_edit_distance_cache("kitten","sitting")
3
>>> compute_edit_distance_cache("ball","football")
4
>>> compute_edit_distance_cache("football","foot")
4

>>> compute_edit_distance_cache("horse","ros")
3
>>> # horse -> rorse (replace "h" with "r")
>>> # rorse -> rose (remove "r")
>>> # rose -> ros (remove "e")

>>> compute_edit_distance_cache("intention","execution")
5
>>> # intention -> inention (remove "t")
>>> # inention -> enention (replace "i" with "e")
>>> # enention -> exention (replace "n" with "x")
>>> # exention -> exection (replace "n" with "c")
>>> # exection -> execution (insert "u")
Parameters:

  • word1 (str) –

  • word2 (str) –

Return type:

int