Levenshtein Edit Distance Metricmedium

Levenshtein Edit Distance Metric

medium Python for AI 15–20 min

NumPy allowed · plain Python earns 10 bonus points

Measure string similarity using the classical Wagner-Fischer dynamic programming edit distance.

Related Skills

Task

Implement edit_distance(word1, word2): calculate the minimum number of operations (insert a character, delete a character, replace a character) needed to transform word1 into word2.

Function Signature

edit_distance(word1: str, word2: str) -> int

Examples

Example 1: Horse to Ros
Input: word1 = 'horse'
word2 = 'ros'
Output: 3

Example 2: Intention to Execution
Input: word1 = 'intention'
word2 = 'execution'
Output: 5

Example 3: Empty Word Against String
Input: word1 = ''
word2 = 'abc'
Output: 3

Constraints

Libraries are allowed; a plain-Python solution earns 10 bonus points.
Words consist of lowercase English letters.
Runs in O(len(word1) * len(word2)) time and space.

Python3Saved ✓

def edit_distance(word1: str, word2: str) -> int:

"""Compute the minimum number of single-character edits (insertions,

deletions, or substitutions) required to transform word1 into word2."""

# Your implementation here

pass

Case 1: Horse to Ros

Input: word1 = 'horse'
word2 = 'ros'

Expected: 3

Case 2: Intention to Execution

Input: word1 = 'intention'
word2 = 'execution'

Expected: 5

Case 3: Empty Word Against String

Input: word1 = ''
word2 = 'abc'

Expected: 3