Implement Levenshtein distance with the iterative two matrix rows optimization. Store…
- 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)).
- 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: 2How it works:
- We keep only two lists:
prev_rowandcurr_row. Each represents a row of the DP table. - For each character in the longer string (
s1), we compute the newcurr_rowbased onprev_row. - 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)
- Insertion:
- After processing each character, we swap
curr_rowwithprev_row. - The answer is the last value in
prev_rowafter the final iteration.
This approach ensures memory usage stays proportional to the length of the shorter string, achieving O(min(n, m)) space.
- We keep only two lists:
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.