Python Challenges: Compute the edit distance between two given strings

Last update on May 28 2022 13:08:57 (UTC/GMT +8 hours)

Python Challenges - 1: Exercise-52 with Solution

From Wikipedia, the free encyclopedia
In computational linguistics and computer science, edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one another by counting the minimum number of operations required to transform one string into the other. Edit distances find applications in natural language processing, where automatic spelling correction can determine candidate corrections for a misspelled word by selecting words from a dictionary that have a low distance to the word in question. In bioinformatics, it can be used to quantify the similarity of DNA sequences, which can be viewed as strings of the letters A, C, G and T.
This problem was asked by Google.
The edit distance between two strings refers to the minimum number of character insertions, deletions, and substitutions required to change one string to the other. For example, the edit distance between "kitten" and "sitting" is three: substitute the "k" for "s", substitute the "e" for "i", and append a "g".
Write a Python program to compute the edit distance between two given strings.

Sample Solution:

Python Code:

def edit_distance(string1, string2):
    """Ref: https://bit.ly/2Pf4a6Z"""

    if len(string1) > len(string2):
        difference = len(string1) - len(string2)
        string1[:difference]

    elif len(string2) > len(string1):
        difference = len(string2) - len(string1)
        string2[:difference]

    else:
        difference = 0

    for i in range(len(string1)):
        if string1[i] != string2[i]:
            difference += 1

    return difference

print(edit_distance("kitten", "sitting")) #3
print(edit_distance("medium", "median")) #2

Sample Output:

3
2

Flowchart:

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program that takes a string of numbers and letters and return string which consists of letters.
Next: Write a Python program to find the largest palindrome made from the product of two 4-digit numbers

Python: Tips of the Day

Find current directory and file's directory:

To get the full path to the directory a Python file is contained in, write this in that file:

import os dir_path = os.path.dirname(os.path.realpath(__file__))

(Note that the incantation above won't work if you've already used os.chdir() to change your current working directory, since the value of the __file__ constant is relative to the current working directory and is not changed by an os.chdir() call.)

To get the current working directory use

import os cwd = os.getcwd()

Documentation references for the modules, constants and functions used above:

The os and os.path modules.

The __file__ constant

os.path.realpath(path) (returns "the canonical path of the specified filename, eliminating any symbolic links encountered in the path")

os.path.dirname(path) (returns "the directory name of pathname path")

os.getcwd() (returns "a string representing the current working directory")

os.chdir(path) ("change the current working directory to path")

Ref: https://bit.ly/3fy0R6m