Edit Distance

Problem

Given two strings, return the minimum number of single-character operations (insert, delete, replace) to convert word1 into word2.

Approach

2D DP where dp[i][j] is the edit distance between the first i characters of word1 and the first j characters of word2. Space-optimized to a single row since each cell only depends on the current and previous row.

When to Use

String similarity / diff algorithms — "minimum edits", "Levenshtein distance", spell checking, DNA sequence alignment. Foundation for fuzzy matching and diff tools. See also: longest_common_subseq.

Complexity

Time	O(m * n)
Space	O(n) (space-optimized)

Implementation

SolutionTestsChallenge

edit_distance

Edit Distance — minimum operations to convert word1 to word2.

Problem

Given two strings, return the minimum number of single-character operations (insert, delete, replace) to convert word1 into word2.

Approach

2D DP where dp[i][j] is the edit distance between the first i characters of word1 and the first j characters of word2. Space-optimized to a single row since each cell only depends on the current and previous row.

When to use

String similarity / diff algorithms — "minimum edits", "Levenshtein distance", spell checking, DNA sequence alignment. Foundation for fuzzy matching and diff tools. See also: longest_common_subseq.

Complexity

Time: O(m * n) Space: O(n) (space-optimized)

edit_distance

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

Return the minimum edit distance between word1 and word2.

edit_distance("horse", "ros") 3 edit_distance("intention", "execution") 5

Source code in src/algo/dp/edit_distance.py

def edit_distance(word1: str, word2: str) -> int:
    """Return the minimum edit distance between *word1* and *word2*.

    >>> edit_distance("horse", "ros")
    3
    >>> edit_distance("intention", "execution")
    5
    """
    m, n = len(word1), len(word2)

    # dp[j] represents the distance for word2[:j]
    dp = list(range(n + 1))

    for i in range(1, m + 1):
        prev = dp[0]
        dp[0] = i
        for j in range(1, n + 1):
            temp = dp[j]
            if word1[i - 1] == word2[j - 1]:
                dp[j] = prev
            else:
                dp[j] = 1 + min(prev, dp[j], dp[j - 1])
            prev = temp

    return dp[n]

tests/dp/test_edit_distance.py

"""Tests for edit distance."""

from hypothesis import given
from hypothesis import strategies as st

from algo.dp.edit_distance import edit_distance


class TestEditDistance:
    def test_horse_ros(self) -> None:
        assert edit_distance("horse", "ros") == 3

    def test_intention_execution(self) -> None:
        assert edit_distance("intention", "execution") == 5

    def test_identical(self) -> None:
        assert edit_distance("abc", "abc") == 0

    def test_empty_to_word(self) -> None:
        assert edit_distance("", "hello") == 5

    def test_word_to_empty(self) -> None:
        assert edit_distance("hello", "") == 5

    def test_both_empty(self) -> None:
        assert edit_distance("", "") == 0

    @given(s=st.text(alphabet="abc", min_size=0, max_size=10))
    def test_symmetric(self, s: str) -> None:
        t = s[::-1]
        assert edit_distance(s, t) == edit_distance(t, s)

Implement it yourself

Run: just challenge dp edit_distance

Then implement the functions to make all tests pass. Use just study dp for watch mode.

Reveal Solution

edit_distance

Edit Distance — minimum operations to convert word1 to word2.

Problem

Given two strings, return the minimum number of single-character operations (insert, delete, replace) to convert word1 into word2.

Approach

2D DP where dp[i][j] is the edit distance between the first i characters of word1 and the first j characters of word2. Space-optimized to a single row since each cell only depends on the current and previous row.

When to use

String similarity / diff algorithms — "minimum edits", "Levenshtein distance", spell checking, DNA sequence alignment. Foundation for fuzzy matching and diff tools. See also: longest_common_subseq.

Complexity

Time: O(m * n) Space: O(n) (space-optimized)

edit_distance

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

Return the minimum edit distance between word1 and word2.

edit_distance("horse", "ros") 3 edit_distance("intention", "execution") 5

Source code in src/algo/dp/edit_distance.py

def edit_distance(word1: str, word2: str) -> int:
    """Return the minimum edit distance between *word1* and *word2*.

    >>> edit_distance("horse", "ros")
    3
    >>> edit_distance("intention", "execution")
    5
    """
    m, n = len(word1), len(word2)

    # dp[j] represents the distance for word2[:j]
    dp = list(range(n + 1))

    for i in range(1, m + 1):
        prev = dp[0]
        dp[0] = i
        for j in range(1, n + 1):
            temp = dp[j]
            if word1[i - 1] == word2[j - 1]:
                dp[j] = prev
            else:
                dp[j] = 1 + min(prev, dp[j], dp[j - 1])
            prev = temp

    return dp[n]