Solving Edit Distance (Levenshtein) in Go: Step-by-Step Guide
Edit distance is one of those classic algorithms that every developer should have in their toolbox. Whether you're building a spell checker, a fuzzy search engine, or a DNA sequence analyzer, understanding how to compute the similarity between two strings is invaluable. In this tutorial, we'll walk through the Levenshtein distance algorithm from theory to a production-ready Go implementation.
What Is Edit Distance (Levenshtein)?
The Levenshtein distance, named after Soviet mathematician Vladimir Levenshtein, measures the minimum number of single-character edits required to transform one string into another. The allowed operations are:
- Insertion — add a character
- Deletion — remove a character
- Substitution — replace one character with another
For example, transforming "kitten" into "sitting" requires three edits: substitute k with s, substitute e with i, and insert g at the end. So the Levenshtein distance is 3.
Why It Matters
Edit distance shows up in surprisingly many places in real-world software:
- Spell checkers — suggest corrections by finding dictionary words with the smallest distance to the misspelled word.
- Fuzzy search — return results even when the user's query contains typos.
- Deduplication — detect near-duplicate records in databases.
- Bioinformatics — compare DNA or protein sequences where insertions, deletions, and mutations naturally occur.
- Natural language processing — measure similarity between tokens or sentences.
- Diff tools — identify minimal changes between two versions of a text.
Because it's so widely applicable, having a fast, correct implementation in your language of choice is genuinely useful. Go, with its excellent performance and simple syntax, is a great fit.
Understanding the Algorithm
The Levenshtein distance is typically solved using dynamic programming. The idea is to build a 2D matrix where the cell at row i and column j represents the edit distance between the first i characters of string a and the first j characters of string b.
The recurrence relation is:
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(
dp[i-1][j], // deletion
dp[i][j-1], // insertion
dp[i-1][j-1] // substitution
)
The base cases are straightforward: transforming any string into an empty string (or vice versa) requires inserting or deleting every character, so dp[i][0] = i and dp[0][j] = j.
Visualizing the Matrix
For "cat" and "cut", the matrix looks like this:
"" c u t
"" 0 1 2 3
c 1 0 1 2
a 2 1 1 2
t 3 2 2 1
The bottom-right cell gives us the answer: 1 (a single substitution of a with u).
Basic Implementation in Go
Let's start with a straightforward 2D matrix implementation. This version is easy to read and mirrors the algorithm description directly.
package main
import "fmt"
func Levenshtein(a, b string) int {
ra := []rune(a)
rb := []rune(b)
m, n := len(ra), len(rb)
// Handle empty string edge cases
if m == 0 {
return n
}
if n == 0 {
return m
}
// Initialize the matrix
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
dp[i][0] = i
}
for j := 0; j <= n; j++ {
dp[0][j] = j
}
// Fill the matrix
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if ra[i-1] == rb[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
del := dp[i-1][j] + 1
ins := dp[i][j-1] + 1
sub := dp[i-1][j-1] + 1
dp[i][j] = min(del, ins, sub)
}
}
}
return dp[m][n]
}
func min(vals ...int) int {
smallest := vals[0]
for _, v := range vals[1:] {
if v < smallest {
smallest = v
}
}
return smallest
}
func main() {
pairs := []struct{ a, b string }{
{"kitten", "sitting"},
{"cat", "cut"},
{"", "abc"},
{"abc", "abc"},
{"flaw", "lawn"},
}
for _, p := range pairs {
fmt.Printf("distance(%q, %q) = %d\n", p.a, p.b, Levenshtein(p.a, p.b))
}
}
Run this and you'll see:
distance("kitten", "sitting") = 3
distance("cat", "cut") = 1
distance("", "abc") = 3
distance("abc", "abc") = 0
distance("flaw", "lawn") = 2
Note the use of []rune instead of indexing the string directly. This is critical in Go because strings are byte sequences, and indexing by byte would break on multi-byte UTF-8 characters like emoji or accented letters.
Space-Optimized Implementation
The basic implementation uses O(m * n) space. However, if you look at the recurrence, each row only depends on the previous row. This means we can reduce the space complexity to O(min(m, n)) by keeping just two rows in memory.
package main
import "fmt"
func LevenshteinOptimized(a, b string) int {
ra := []rune(a)
rb := []rune(b)
// Ensure b is the shorter string to minimize memory
if len(ra) < len(rb) {
ra, rb = rb, ra
}
m, n := len(ra), len(rb)
if n == 0 {
return m
}
previous := make([]int, n+1)
current := make([]int, n+1)
for j := 0; j <= n; j++ {
previous[j] = j
}
for i := 1; i <= m; i++ {
current[0] = i
for j := 1; j <= n; j++ {
cost := 1
if ra[i-1] == rb[j-1] {
cost = 0
}
del := previous[j] + 1
ins := current[j-1] + 1
sub := previous[j-1] + cost
current[j] = min(del, ins, sub)
}
previous, current = current, previous
}
return previous[n]
}
func min(vals ...int) int {
smallest := vals[0]
for _, v := range vals[1:] {
if v < smallest {
smallest = v
}
}
return smallest
}
func main() {
fmt.Println(LevenshteinOptimized("kitten", "sitting")) // 3
fmt.Println(LevenshteinOptimized("café", "cafe")) // 1
}
This version is functionally identical but far more memory-efficient. For comparing long strings — say, two 10,000-character documents — the difference is dramatic: the basic version allocates 100 million integers, while the optimized version allocates only 10,000.
Adding a Normalized Similarity Score
Raw edit distances are useful, but sometimes you want a similarity score between 0 and 1, where 1 means identical and 0 means completely different. You can normalize the distance by dividing it by the length of the longer string.
package main
import "fmt"
func Similarity(a, b string) float64 {
if a == b {
return 1.0
}
ra := []rune(a)
rb := []rune(b)
maxLen := len(ra)
if len(rb) > maxLen {
maxLen = len(rb)
}
if maxLen == 0 {
return 1.0
}
dist := LevenshteinOptimized(a, b)
return 1.0 - float64(dist)/float64(maxLen)
}
func main() {
fmt.Printf("%.2f\n", Similarity("kitten", "sitting")) // 0.57
fmt.Printf("%.2f\n", Similarity("cat", "cut")) // 0.67
fmt.Printf("%.2f\n", Similarity("hello", "hello")) // 1.00
}
This is handy when you need to threshold results — for example, "show me all records with at least 80% similarity to the query."
Building a Simple Fuzzy Search
Let's put everything together into a practical example: a fuzzy search function that finds the closest matches from a list of candidates.
package main
import (
"fmt"
"sort"
)
type Match struct {
Word string
Distance int
Similarity float64
}
func FuzzySearch(query string, candidates []string, maxDistance int) []Match {
var matches []Match
for _, c := range candidates {
d := LevenshteinOptimized(query, c)
if d <= maxDistance {
matches = append(matches, Match{
Word: c,
Distance: d,
Similarity: Similarity(query, c),
})
}
}
sort.Slice(matches, func(i, j int) bool {
return matches[i].Distance < matches[j].Distance
})
return matches
}
func main() {
dictionary := []string{
"apple", "apply", "banana", "grape",
"orange", "peach", "pear", "pineapple",
}
results := FuzzySearch("aple", dictionary, 3)
for _, m := range results {
fmt.Printf("%-10s distance=%d similarity=%.2f\n",
m.Word, m.Distance, m.Similarity)
}
}
Output:
apple distance=1 similarity=0.80
apply distance=2 similarity=0.60
grape distance=3 similarity=0.40
This is the foundation of a spell checker. You could extend it by weighting substitutions differently (for example, a and e are commonly confused and could cost less than a and z), or by incorporating keyboard layout proximity.
Writing Tests
Any algorithm implementation deserves proper tests. Here's a test suite using Go's standard testing package:
package levenshtein
import "testing"
func TestLevenshtein(t *testing.T) {
tests := []struct {
name string
a, b string
expected int
}{
{"identical", "abc", "abc", 0},
{"empty first", "", "abc", 3},
{"empty second", "abc", "", 3},
{"both empty", "", "", 0},
{"single substitution", "cat", "cut", 1},
{"classic example", "kitten", "sitting", 3},
{"unicode", "café", "cafe", 1},
{"emoji", "😀abc", "abc", 1},
{"complete replacement", "abc", "xyz", 3},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
got := LevenshteinOptimized(tt.a, tt.b)
if got != tt.expected {
t.Errorf("Levenshtein(%q, %q) = %d, want %d",
tt.a, tt.b, got, tt.expected)
}
})
}
}
func TestLevenshteinSymmetry(t *testing.T) {
pairs := []struct{ a, b string }{
{"kitten", "sitting"},
{"flaw", "lawn"},
{"gumbo", "gambol"},
}
for _, p := range pairs {
forward := LevenshteinOptimized(p.a, p.b)
backward := LevenshteinOptimized(p.b, p.a)
if forward != backward {
t.Errorf("distance(%q,%q)=%d but distance(%q,%q)=%d",
p.a, p.b, forward, p.b, p.a, backward)
}
}
}
The symmetry test is a nice property-based check: Levenshtein distance should always be the same regardless of argument order, since every insertion in one direction is a deletion in the other.
Best Practices
Always Use Runes for Unicode Safety
Go strings are UTF-8 encoded byte slices. If you index a string containing multi-byte characters directly with s[i], you'll get individual bytes, not characters. Always convert to []rune first. This ensures your implementation works correctly with accented characters, CJK scripts, and emoji.
Choose the Right Variant for Your Use Case
- Use the basic 2D matrix version when clarity matters more than memory — for example, in educational code or when you also need to reconstruct the edit path.
- Use the two-row optimized version in production, especially when comparing long strings or running many comparisons.
- If you only need to know whether the distance is below a threshold (not the exact value), you can add early termination by pruning cells that exceed the threshold, reducing time complexity significantly.
Consider Weighted Variants
Standard Levenshtein treats all edits equally, but real applications often benefit from weighted costs. For example, in OCR correction, substituting visually similar characters (0 and O) should cost less than substituting dissimilar ones. You can extend the algorithm by replacing the fixed cost of 1 with a cost function.
Benchmark Before Optimizing Further
The two-row version is fast enough for most use cases. If you need to compare millions of strings, consider using a Trie-based approach or the Bitap algorithm, which can skip irrelevant comparisons entirely. Always benchmark with realistic data before choosing a more complex algorithm.
func BenchmarkLevenshtein(b *testing.B) {
for i := 0; i < b.N; i++ {
LevenshteinOptimized("kitten", "sitting")
}
}
Cache Results When Appropriate
If you're repeatedly comparing the same pairs — for instance, ranking a fixed dictionary against many user queries — consider caching the dictionary's preprocessed representations or memoizing results with an LRU cache.
Conclusion
The Levenshtein distance is a deceptively simple algorithm with deep practical utility. In this guide, we covered what it is, why it matters, and how to implement it correctly and efficiently in Go — starting from a readable 2D matrix version, moving to a space-optimized two-row version, and building up to a practical fuzzy search tool. Along the way, we emphasized Unicode safety through rune conversion, proper testing, and performance considerations. With these building blocks, you're well-equipped to add fuzzy matching, spell checking, or similarity scoring to your Go applications. The algorithm is small enough to fit in a single function, yet powerful enough to solve real problems — and that's exactly what makes it a timeless piece of every developer's toolkit.