Implement a Python function to calculate the Levenshtein distance between strings.
- User
Implement a Python function to calculate the Levenshtein distance between strings.
- Assistant
Implementing Levenshtein Distance Function
The user wants a Python function to calculate the Levenshtein distance between two strings using a concise dynamic programming (DP) approach. I need to ensure the implementation is correct, including edge cases and type validation, while explaining the method briefly. The function should handle deletions, insertions, substitutions—all with equal cost of 1—and should be annotated properly. The expected time complexity is O(mn), and I’ll make sure it’s concise, avoiding emojis. Here’s a straightforward dynamic programming implementation of Levenshtein distance in Python:
def levenshtein_distance(s1: str, s2: str) -> int: """ Compute the Levenshtein distance between two strings s1 and s2. The distance is the minimum number of single-character edits (insertions, deletions or substitutions) required to change s1 into s2. """ m, n = len(s1), len(s2) # If one of the strings is empty, distance is the length of the other if m == 0: return n if n == 0: return m # dp[i][j] = distance between s1[:i] and s2[:j] dp = [[0] * (n + 1) for _ in range(m + 1)] # Initialize base cases for i in range(m + 1): dp[i][0] = i # deletions for j in range(n + 1): dp[0][j] = j # insertions for i in range(1, m + 1): for j in range(1, n + 1): cost = 0 if s1[i - 1] == s2[j - 1] else 1 dp[i][j] = min( dp[i - 1][j] + 1, # deletion dp[i][j - 1] + 1, # insertion dp[i - 1][j - 1] + cost # substitution ) return dp[m][n]Example usage:
print(levenshtein_distance("kitten", "sitting")) # 3 print(levenshtein_distance("flaw", "lawn")) # 2
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.