Edit distance

A catalog search gets a product name with a typo. Exact equality finds nothing, but the app can compare the query with a small candidate list and rank names by how many character edits separate them.

Trying every possible edit sequence repeats the same comparisons. Levenshtein distance records answers for pairs of prefixes, using insertion, deletion, and substitution at unit cost. It measures those edits, not whether two names mean the same thing.

Ranking a misspelled catalog query

Levenshtein distance compares prefixes. A cell may delete the left suffix character, insert the right suffix character, or align the two final characters with substitution cost zero or one. All three dependencies lie in the previous row or the current row's previous cell.

Comparing prefixes instead of edit sequences

For ab and acb, inserting c is enough. A table cell describes a pair of prefix lengths, not two character indices. Its final step either deletes from the left, inserts from the right, or aligns both final characters with a match or substitution. Only the previous row and current row's preceding cell are needed to compute the next value.

Text left = U"a", right = U"acb";
std::vector<Int> previous{0, 1, 2, 3}, current{1};
std::size_t j = 1; // First cell: prefix "a" against prefix "a".
Int cost = left[0] == right[j - 1] ? 0 : 1;
current.push_back(std::min({previous[j] + 1, current[j - 1] + 1,
                           previous[j - 1] + cost}));
std::cout << current[1] << '\n'; // 0: match rather than insert or delete.
// A transposition is still not one Levenshtein edit: "ab" to "ba" needs two.

Distance is not the whole search engine

Distance-only output permits discarding old rows. Keep the shorter string on the column axis so auxiliary memory is O(min(n,m)), and retain the old diagonal before overwriting a cell. The first row and column encode converting to or from an empty prefix. Text preserves code-point semantics; UTF-8 byte distance would overcharge many non-ASCII edits. Canonical equivalence is not assumed: a composed accent and a combining sequence can have different lengths and edit distance. An uncached recursive prototype demonstrates the recurrence but repeats a large tree of overlapping subproblems.

The recurrence evaluates O(nm) prefix pairs. Two rows use O(min(n,m)) DP storage when the shorter text indexes columns, in addition to any decoded input arrays. Returning an edit script needs extra reconstruction work. Transposing adjacent symbols is not a single Levenshtein edit.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged. Text ordering follows Unicode code points (Text) or the documented UTF-8 identifier order (std::string).

A production catalog still needs a way to find plausible candidates before comparing their edit distances.