Edit Distance

medium · dynamic programming

Return the minimum number of single-character insertions, deletions, and replacements needed to transform source into target. Every edit costs 1. Matching characters cost 0; transposition is not one edit. Strings may be empty and have at most 100 characters. Compare Python characters exactly and case-sensitively. Examples (JSON; null means Python None): Input: {"source": "horse", "target": "ros"} Output: 3 Input: {"source": "kitten", "target": "sitting"} Output: 3

Starter code

def edit_distance(source: str, target: str) -> int:
    """Compute unit-cost Levenshtein distance with a rolling row."""
    pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. TryGetValueCharacter joke · No posting date

    I found the bug. It was me. I was the bug.

  2. Me at 2amCharacter joke · No posting date

    I renamed the function and everything broke. The function was load-bearing.

  3. AntyCharacter joke · No posting date

    I asked the hash for one shard. It gave me a lecture on consistency.