Introduction

Standard Levenshtein distance counts every substitution as equally expensive, but typographical errors are not uniform. Replacing h with j is much more plausible on a QWERTY keyboard than replacing h with p, so a spelling metric that understands keyboard geometry often produces better rankings for search, autocorrect, and fuzzy matching.

Start with Weighted Edit Distance

The right starting point is still dynamic programming. The difference is that insertion, deletion, substitution, and optionally transposition use custom costs instead of a fixed value of 1.

For keyboard-aware matching, substitutions between nearby keys should be cheap, substitutions between distant keys should be expensive, and insertions and deletions usually keep a constant penalty.

1from math import inf
2
3ROWS = ["qwertyuiop", "asdfghjkl", "zxcvbnm"]
4POSITIONS = {
5    ch: (row_index, col_index)
6    for row_index, row in enumerate(ROWS)
7    for col_index, ch in enumerate(row)
8}
9
10
11def substitution_cost(left: str, right: str) -> float:
12    if left == right:
13        return 0.0
14
15    a = POSITIONS.get(left.lower())
16    b = POSITIONS.get(right.lower())
17    if a is None or b is None:
18        return 1.5
19
20    distance = abs(a[0] - b[0]) + abs(a[1] - b[1])
21    if distance == 1:
22        return 0.35
23    if distance == 2:
24        return 0.75
25    return 1.5

This cost function is intentionally simple. In production you may tune the values with observed typo data, but even a basic adjacency model improves relevance noticeably.

Add the Cost Function to Levenshtein

Once the substitution cost is keyboard-aware, the main algorithm barely changes. The matrix still represents the cheapest way to transform one prefix into another.

1def qwerty_weighted_distance(source: str, target: str) -> float:
2    rows = len(source) + 1
3    cols = len(target) + 1
4    dp = [[0.0] * cols for _ in range(rows)]
5
6    for i in range(1, rows):
7        dp[i][0] = i * 1.0
8    for j in range(1, cols):
9        dp[0][j] = j * 1.0
10
11    for i in range(1, rows):
12        for j in range(1, cols):
13            insert_cost = dp[i][j - 1] + 1.0
14            delete_cost = dp[i - 1][j] + 1.0
15            replace_cost = dp[i - 1][j - 1] + substitution_cost(
16                source[i - 1],
17                target[j - 1],
18            )
19
20            best = min(insert_cost, delete_cost, replace_cost)
21
22            if (
23                i > 1
24                and j > 1
25                and source[i - 1] == target[j - 2]
26                and source[i - 2] == target[j - 1]
27            ):
28                best = min(best, dp[i - 2][j - 2] + 0.4)
29
30            dp[i][j] = best
31
32    return dp[-1][-1]
33
34
35tests = [
36    ("hello", "gello"),
37    ("hello", "jello"),
38    ("hello", "pello"),
39    ("form", "from"),
40]
41
42for left, right in tests:
43    print(left, right, qwerty_weighted_distance(left, right))

The transposition rule makes this closer to weighted Damerau-Levenshtein, which is often a better model for typing errors because swapped adjacent letters are common.

Why This Beats Plain Levenshtein

A normal Levenshtein distance would give the same substitution penalty to hello versus jello and hello versus pello. A keyboard-aware distance makes jello cheaper because j sits next to h, while p is much farther away. That changes result ordering in a way users usually perceive as more natural.

This matters in:

• spell check suggestions
• search queries with typing errors
• username or product lookup
• ranking candidates after a broad fuzzy prefilter

The point is not that the distance becomes linguistically perfect. It becomes better aligned with how real mistypes happen on a physical keyboard.

Common Pitfalls

One mistake is overfitting the weights too early. If adjacent substitutions are nearly free, unrelated words can collapse into the same score band and ranking quality gets worse. Start with moderate cost differences and tune only when you have actual typo data.

Another issue is ignoring layout differences. QWERTY weights are appropriate for a QWERTY keyboard. If your users type on AZERTY, Dvorak, or mobile touch keyboards, the geometry changes and so should the substitution map.

Case handling also matters. Most implementations should normalize case before scoring, or else A versus a may accidentally be treated as an unknown-key substitution with an inflated cost.

Finally, remember that edit distance is only one feature. For search ranking, combine it with prefix matches, word frequency, and domain knowledge. A perfect typo model can still return bad results if the rest of the ranking stack is weak.

Summary

• Use weighted edit distance when nearby keyboard keys should be cheaper substitutions.
• Keep the dynamic programming structure from Levenshtein and replace fixed substitution cost with a keyboard-based function.
• Add transposition support if swapped letters are common in your workload.
• Tune weights with care instead of making adjacent keys nearly free.
• Match the keyboard model to your users, not just to your own layout.