Levenshtein distance: a practical guide to string similarity

Levenshtein distance measures how much two strings differ by counting the smallest number of single-character insertions, deletions and substitutions needed to turn one into the other. A value of zero means the strings are identical, while one means a single edit is enough. The measure is useful whenever a system must tolerate typos, missing characters, transposed-looking input or inconsistent formatting.

This guide develops the metric from its dynamic programming matrix to a working Python implementation, then examines memory use, thresholds and common failure modes. The aim is practical rather than theoretical: by the end, you should be able to explain a distance value, recover an edit script and choose when a faster or more specialised algorithm is appropriate.

What the distance measures

Each permitted operation has a cost of one. Insertion adds a character, deletion removes one, and substitution replaces one character with another. Matching characters cost nothing. Levenshtein distance is therefore the minimum total cost over all valid sequences of edits, not merely the number of positions at which two equal-length strings happen to differ.

This makes it different from Hamming distance, which counts substitutions only and assumes equal lengths. It also differs from a raw comparison of character counts: two strings can contain the same letters in a different order yet still require several edits. Because an optimal sequence may change the alignment of many characters, a small distance is a useful signal of similarity but not a proof of shared meaning.

Consider the Australian place name “Brisbane” and the plausible typo “Brisbain”. One substitution changes the final e to i, so their distance is one. The same idea applies across Australian English and international spellings: “organise” and “organize” need one replacement, while “favourite” and “favorite” need one deletion. These small examples show why the metric suits search boxes and catalogue matching.

Building the dynamic programming matrix

Let the first string be x with length m and the second be y with length n. Define d[i][j] as the distance between the first i characters of x and the first j characters of y. The cell d[0][j] equals j because j insertions are needed to build the second prefix from an empty string; similarly, d[i][0] equals i.

Every other cell takes the cheapest of three routes: delete x[i-1], insert y[j-1], or match or replace the two final characters. The recurrence is:

d[i][j] = min(
    d[i-1][j] + 1,
    d[i][j-1] + 1,
    d[i-1][j-1] + cost
)

Here, cost is zero when x[i-1] == y[j-1] and one otherwise.

The final answer is d[m][n]. Filling the table row by row works because each route depends only on the cell above, the cell to the left, or the upper-left cell. If an edit script is needed, store which route produced each minimum and trace backwards from the bottom-right cell; reversing the recovered operations produces one optimal transformation.

Following an edit script

Take “kitten” and “sitting”. A low-cost sequence replaces k with s, replaces e with i, then inserts g at the end, giving a distance of three. Another valid sequence may cost the same while choosing different intermediate edits; optimal means that no cheaper sequence exists, not that the recovered script is unique.

The full matrix for these words exposes the calculation:

        ""  s  i  t  t  i  n
  ""     0  1  2  3  4  5  6
  k      1  1  2  3  4  5  6
  i      2  2  1  2  3  4  5
  t      3  3  2  2  2  3  4
  t      4  4  3  3  2  3  4
  e      5  5  4  4  3  3  4
  n      6  6  5  5  4  4  3

Reading the last row shows three while the first column counts deletions from the left. A traceback can move from the bottom-right corner to the upper-left, recording substitutions on diagonal steps, insertions on horizontal steps and deletions on vertical steps. That path is often more informative than the scalar value when a user needs to understand a suggested correction.

Implementing the method in Python

A compact implementation needs only the previous and current matrix rows:

def levenshtein_distance(source: str, target: str) -> int:
    if len(source) < len(target):
        source, target = target, source

    previous = list(range(len(target) + 1))

    for row, source_char in enumerate(source, start=1):
        current = [row]

        for column, target_char in enumerate(target, start=1):
            substitution_cost = (
                0 if source_char == target_char else 1
            )

            current.append(min(
                previous[column] + 1,
                current[column - 1] + 1,
                previous[column - 1] + substitution_cost,
            ))

        previous = current

    return previous[-1]

Swapping the strings keeps the shorter one in the working row, so auxiliary space is O(min(m, n)) rather than O(mn). Time remains O(mn) because every pair of character positions is considered. The returned value is an integer, and the function leaves the input strings unchanged.

Basic checks make the behaviour easier to trust: the empty string against “Melbourne” returns eight, identical strings return zero, and “Brisbane” against “Brisbain” returns one. Unit tests should also cover repeated characters and Unicode text. Readers wanting more drills can use the site's problem-solving guides to practise tracing matrices before optimising the implementation.

Optimising memory and runtime

Keeping the whole matrix is worthwhile only when you need the edit script or per-cell values. For a simple score, retain one row and replace it as each new row is calculated. The code above already does this. More generally, dynamic programming can also find the best matching suffix or approximate substring by changing how the first row is initialised.

Very large inputs need a different strategy. A bounded search can stop expanding cells once their cost exceeds the best accepted match, which is useful for spelling suggestions with a maximum distance. Bit-parallel implementations pack many comparison states into machine words and can be much faster in compiled libraries; specialised fuzzy-search tools may offer more than plain Levenshtein.

Distance also has a useful conceptual connection to graph algorithms. Graph search has a similar need to compare alternative routes: this explanation of Prim’s algorithm overview shows how edge weights guide a minimum spanning tree, whereas character comparison uses edit costs. Both problems assign costs to alternatives and choose a minimum, but one acts on edges and the other on characters.

Useful applications and hidden pitfalls

Common uses include ranking spelling corrections, matching abbreviated product names, deduplicating records and finding likely duplicates in names or addresses. A search interface can retrieve candidates with a small distance, then apply stricter rules such as category, postcode or price. The metric is especially useful as a transparent baseline because its score can be explained as concrete edits.

Edit distance can also be one feature among many, rather than the entire model; the neural network fundamentals explain how such inputs can be combined during supervised learning. A learned model may recognise patterns that raw character counts miss, but a distance feature remains easy to inspect and can be computed before inference.

Several limitations deserve attention. Ordinary Levenshtein distance charges two edits for an adjacent transposition, so “teh” versus “the” may justify Damerau-Levenshtein distance. Case, accents, punctuation and whitespace can dominate a score unless they are normalised consistently. Finally, no universal threshold works: a one-character difference may be harmless in a long suburb name but serious in a short product code.

A practical checklist for Australian projects

Australian inputs make normalisation especially important. Australian English spellings such as “favourite” and “organise” may appear beside “favorite” and “organize” in imported feeds, direct-to-consumer campaigns or international marketplace listings. Australian online grocery and general merchandise marketplaces often combine supplier catalogues with listings from multiple sellers, so the same item can appear as “chicken breast”, “Chicken Breast” or “chicken-breast”. Flexible matching can retrieve these variants, but canonicalisation should happen before scoring.

Local language and place names add useful test cases. “Arvo” for afternoon, “servo” for a petrol station and “barbie” for a barbecue are common Australian usages, while misspellings of Brisbane, Canberra, Darwin, Melbourne, Perth and Adelaide can occur in search queries. Protecting these terms from automatic correction avoids changing meaning. A practical preprocessing checklist is:

• Apply Unicode NFC normalisation and decide whether letter case matters.
• Collapse repeated whitespace while preserving meaningful punctuation.
• Protect product codes, SKUs, URLs and recognised place names from correction.
• Map agreed Australian and international spelling variants to one canonical form.

After preprocessing, evaluate the matcher against representative Australian queries rather than an arbitrary similarity cutoff:

• Measure exact-match recall and fuzzy-match recall separately.
• Report precision at each accepted similarity threshold.
• Record p95 latency for customer-facing autocomplete and search.
• Review false matches by language, product category and spelling convention.

Levenshtein distance is most effective when its assumptions match the data. It gives a compact, explainable similarity score, works well for short strings and provides a strong baseline for fuzzy matching. Larger datasets or semantic intent require additional signals, but understanding the edit costs remains a reliable foundation for building those systems.