The Levenshtein distance, also known as the edit distance, measures the minimum number of single-character edits required to transform one string into another. These edits can be insertions, deletions, or substitutions.

levenshtein_distance.py

def levenshtein_distance(str1, str2):
    m, n = len(str1), len(str2)
    
    # Initialize a matrix to store distances
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Fill the matrix with base cases
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],      # Deletion
                                  dp[i][j - 1],      # Insertion
                                  dp[i - 1][j - 1])  # Substitution
    
    return dp[m][n]

# Example Usage
str1 = "kitten"
str2 = "sitting"
distance = levenshtein_distance(str1, str2)
print(f"Levenshtein Distance between '{str1}' and '{str2}': {distance}")