37. Fuzzy-Match a Voice Command

Problem

A voice assistant's ASR transcript of a spoken command is rarely a perfect string — background noise, accents, or a dropped phoneme can turn “turn on the lights” into “turn on the lihgts.”

Given the noisy transcript and a fixed list of canonical commands the system understands, find the canonical command whose Levenshtein edit distance to the transcript is smallest, as long as that distance is within a tolerance threshold. Ties go to whichever command is listed earliest; if nothing is within tolerance, there's no confident match.

Source: src/37_fuzzy_match_voice_command.py

def fuzzy_match_command(query: str, commands: list[str], max_distance: int) -> str | None:
    ...

Examples:
>>> fuzzy_match_command(
...     "turn on the lihgts",
...     ["turn on the lights", "turn off the lights", "set a timer"],
...     3,
... )
'turn on the lights'

>>> fuzzy_match_command("xyz completely different", ["turn on the lights", "set a timer"], 3)
# None

Step-by-Step Approach

1. Recognize the core subroutine is Levenshtein edit distance, applied once per candidate command rather than once overall.
2. Build the standard O(len(query) · len(command)) DP table for edit distance: each cell is the minimum edits (insert, delete, substitute) to turn one prefix into the other.
3. Loop over every canonical command, computing its distance to the query and tracking the best (smallest) distance seen so far along with which command achieved it.
4. Use a strict less-than comparison when updating the best match, so the first command to reach a given distance keeps priority over a later one that only ties it — that's what makes tie-breaking deterministic.
5. After scanning every command, compare the best distance found to max_distance: if it's within tolerance return that command, otherwise return None.
6. Handle the empty-command-list edge case naturally: no command is ever considered, so the best-distance sentinel never gets beaten and the function returns None.

The key insight is that fuzzy matching against a list is just single-target edit distance run in a loop with a running best-so-far — the interesting part isn't the DP itself (that's a known subroutine) but getting the tie-break and threshold check right around it.

Reference solution

def _edit_distance(a: str, b: str) -> int:
    # standard Levenshtein DP, O(len(a) * len(b)) time, O(len(b)) space (rolling rows)
    m, n = len(a), len(b)
    prev = list(range(n + 1))
    for i in range(1, m + 1):
        curr = [i] + [0] * n
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
        prev = curr
    return prev[n]


def fuzzy_match_command(query: str, commands: list[str], max_distance: int) -> str | None:
    best_command: str | None = None
    best_distance = max_distance + 1  # anything found must beat this to count
    for command in commands:
        distance = _edit_distance(query, command)
        # strict '<' keeps the earliest-listed command on ties
        if distance < best_distance:
            best_distance = distance
            best_command = command
    return best_command if best_distance <= max_distance else None


TEST_CASES = [
    {
        "input": {
            "query": "turn on the lihgts",
            "commands": ["turn on the lights", "turn off the lights", "set a timer"],
            "max_distance": 3,
        },
        "expected": "turn on the lights",
    },
    {
        "input": {
            "query": "xyz completely different",
            "commands": ["turn on the lights", "set a timer"],
            "max_distance": 3,
        },
        "expected": None,
    },
    {
        "input": {"query": "set a timer", "commands": ["set a timer", "stop the timer"], "max_distance": 0},
        "expected": "set a timer",
    },
    {
        "input": {"query": "cat", "commands": ["cot", "cap"], "max_distance": 1},
        "expected": "cot",
    },
    {
        "input": {"query": "anything", "commands": [], "max_distance": 5},
        "expected": None,
    },
]


def main():
    for i, case in enumerate(TEST_CASES):
        query = case["input"]["query"]
        commands = case["input"]["commands"]
        max_distance = case["input"]["max_distance"]
        expected = case["expected"]
        print(f"Test {i}: fuzzy_match_command(query={query!r}, commands={commands}, max_distance={max_distance})")
        for command in commands:
            d = _edit_distance(query, command)
            print(f"  dist({query!r}, {command!r}) = {d}")
        result = fuzzy_match_command(query=query, commands=commands, max_distance=max_distance)
        assert result == expected
        print(f"PASSED: {result!r}")
    print(f"All {len(TEST_CASES)} test cases passed.")


if __name__ == "__main__":
    main()

Key Functions & Tricks

• _edit_distance(a, b) — rolling-row Levenshtein DP, O(len(a) · len(b)) time, O(min(len(a), len(b))) space
• best_distance = max_distance + 1 — sentinel that only a real, in-tolerance match can beat
• if distance < best_distance — strict comparison keeps the earliest-listed command on ties
• best_command if best_distance <= max_distance else None — final tolerance gate before returning

How to Recognize This Pattern