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

Implement Levenshtein distance with the iterative two matrix rows optimization. Store…

  1. User

    Implement Levenshtein distance with the iterative two matrix rows optimization. Store only current and previous row instead of the full matrix to reduce space complexity to O(min(n,m)).

  2. Assistant

    Implementing optimized Levenshtein distance

    Providing a Python function computing Levenshtein distance with only two matrix rows stored, reducing space to O(min(n,m)); it swaps inputs to minimize space usage and uses clear comments to explain steps. Below is a Python implementation of the Levenshtein distance that uses only two rows of the dynamic programming table, reducing space complexity to O(min(n, m)):

    def levenshtein_distance(s1: str, s2: str) -> int:
        # If one string is empty, distance is simply the other string's length
        if len(s1) == 0:
            return len(s2)
        if len(s2) == 0:
            return len(s1)
    
        # To save space, ensure s2 is the shorter string
        if len(s1) < len(s2):
            s1, s2 = s2, s1
    
        # Previous row: cost of transforming empty prefix of s1 to prefixes of s2
        prev_row = list(range(len(s2) + 1))
        curr_row = [0] * (len(s2) + 1)
    
        for i, c1 in enumerate(s1, start=1):
            # First element of current row: cost of deleting all characters from s1's prefix
            curr_row[0] = i
    
            for j, c2 in enumerate(s2, start=1):
                # Insertion cost: curr_row[j-1] + 1
                # Deletion cost: prev_row[j] + 1
                # Substitution cost: prev_row[j-1] + (1 if different else 0)
                insert_cost = curr_row[j - 1] + 1
                delete_cost = prev_row[j] + 1
                substitute_cost = prev_row[j - 1] + (c1 != c2)
    
                curr_row[j] = min(insert_cost, delete_cost, substitute_cost)
    
            # Swap rows for next iteration
            prev_row, curr_row = curr_row, prev_row
    
        # The last computed 'prev_row' contains the final distances
        return prev_row[len(s2)]
    
    
    # Example usage:
    if __name__ == "__main__":
        print(levenshtein_distance("kitten", "sitting"))  # Output: 3
        print(levenshtein_distance("flaw", "lawn"))       # Output: 2
    

    How it works:

    1. We keep only two lists: prev_row and curr_row. Each represents a row of the DP table.
    2. For each character in the longer string (s1), we compute the new curr_row based on prev_row.
    3. The recurrence relation:
      • Insertion: curr_row[j-1] + 1
      • Deletion: prev_row[j] + 1
      • Substitution: prev_row[j-1] + (1 if c1 != c2 else 0)
    4. After processing each character, we swap curr_row with prev_row.
    5. The answer is the last value in prev_row after the final iteration.

    This approach ensures memory usage stays proportional to the length of the shorter string, achieving O(min(n, m)) space.

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