Skip to content
TheChatArchiveThe Chat Archive
GPT 5.1· openaiHugging Face Frontier Reasoning Traces

Implement a Python function to calculate the Levenshtein distance between strings.

  1. User

    Implement a Python function to calculate the Levenshtein distance between strings.

  2. 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
    

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.