bigcode/bigcode-playground · def levenshtein

Question:

def levenshtein_distance(s1, s2):
Answer:

def levenshtein_distance(s1, s2):
    """Calculates the Levenshtein distance between two strings.


    The Levenshtein distance is defined as the number of additions, deletions or substitutions required to transform one string into another. This can be thought of as a measure of similarity between two sequences. It differs from the standard edit distance in that it allows for transpositions and replaces all insertions with deletions.


    Args:
        s1 (str): first string
        s2 (str): second string


    Returns:
        int: Levenshtein distance between `s1` and `s2`. If both are equal then 0 is returned.
    """
    if len(s1) < len(s2):
        return levenshtein_distance(s2, s1)


    # len(s1) >= len(s2)
    if len(s2) == 0:
        return len(s1)


    previous_row = xrange(len(s2)+1)
    for i, c1 in enumerate(s1):
        current_row = [i+1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1 # j+1 instead of j since previous_row and current_row are one character longer
            deletions = current_row[j] + 1       # than s2
            substitutions = previous_row[j] + (c1!= c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row


    return previous_row[-1]
<|endoftext|>