23. Fuzzy-Match a KB Title

Problem

When exact or embedding search over the knowledge base comes back empty for a raw customer query, a typo-tolerant fallback can help: compute the edit distance between the query and each candidate KB article title, and treat low-distance titles as plausible matches worth surfacing anyway.

Given two strings a and b, return the Levenshtein distance between them — the minimum number of single-character insertions, deletions, or substitutions needed to turn a into b.

Source: src/23_fuzzy_match_kb_title.py

def edit_distance(a: str, b: str) -> int:
    ...

>>> edit_distance("kitten", "sitting")
3

>>> edit_distance("horse", "ros")
3

>>> edit_distance("abc", "abc")
0

Step-by-Step Approach

1. Define dp[i][j] as the edit distance between the first i characters of a and the first j characters of b. Build a (len(a)+1) x (len(b)+1) table.
2. Base cases: turning an empty prefix of a into a j-length prefix of b takes j insertions, so dp[0][j] = j. Symmetrically dp[i][0] = i (all deletions).
3. For each i from 1 to len(a) and j from 1 to len(b): if a[i-1] == b[j-1], the last characters already match, so no extra edit is needed: dp[i][j] = dp[i-1][j-1].
4. Otherwise the last characters differ, so take the best of three options and add 1: delete from a (dp[i-1][j]), insert into a (dp[i][j-1]), or substitute (dp[i-1][j-1]).
5. Fill the table row by row (or column by column) in increasing order of i and j, since each cell only depends on cells with smaller or equal indices.
6. The answer is dp[len(a)][len(b)], the bottom-right corner.

The key insight is that the edit distance between two prefixes reduces to a choice among the edit distances of three smaller prefix pairs, which is exactly what makes it amenable to bottom-up DP rather than exponential brute-force recursion.

Reference solution

def edit_distance(a: str, b: str) -> int:
    # classic bottom-up DP table, dp[i][j] = distance between a[:i] and b[:j]; O(len(a)*len(b))
    m, n = len(a), len(b)
    # fresh row list per iteration, not aliased
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        # base case: i deletions to turn a[:i] into empty
        dp[i][0] = i
    for j in range(n + 1):
        # base case: j insertions to turn empty into b[:j]
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # a[i-1]/b[j-1]: current chars for prefixes of length i/j
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                # delete/insert/substitute
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]

Key Functions & Tricks

• [[0] * (n + 1) for _ in range(m + 1)] — fresh row lists per iteration, avoids row aliasing.
• dp[i][0] = i / dp[0][j] = j — base cases: all deletions / all insertions.
• a[i - 1] == b[j - 1] — off-by-one: row/col i/j means length-i/j prefix.
• min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) — cheapest of delete/insert/substitute, O(1) per cell.

How to Recognize This Pattern