Edit Distance (Levenshtein)
Derive the edit-distance recurrence for insert/delete/replace operations and fill the DP table for pairs of strings of varying length.
Edit Distance (Levenshtein) is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Edit Distance Problem
Edit Distance (Levenshtein distance, LeetCode 72) asks: what is the minimum number of insert, delete, or replace operations needed to transform one string into another? For example, to transform 'horse' into 'ros': replace 'h'→'r' (horse→rorse), delete 'r' (rorse→rose), delete 'e' (rose→ros) — 3 operations. Edit distance is foundational in spell-checkers, DNA alignment, and fuzzy matching.
# Allowed operations:
# Insert: 'abc' → 'abXc' (insert X)
# Delete: 'abc' → 'ac' (delete b)
# Replace: 'abc' → 'aXc' (replace b with X)
# horse → ros: 3 operations
# 1. horse → rorse (replace h with r)
# 2. rorse → rose (delete r at index 1)
# 3. rose → ros (delete e)
print('Edit distance horse→ros: 3')
print('Edit distance intention→execution: 5')DP State and Recurrence
Define dp[i][j] = minimum edit distance between word1[:i] and word2[:j]. If word1[i-1] == word2[j-1], no operation needed: dp[i][j] = dp[i-1][j-1]. Otherwise, take the minimum of three operations: insert dp[i][j-1] + 1, delete dp[i-1][j] + 1, replace dp[i-1][j-1] + 1. Base cases: dp[i][0] = i (delete all of word1) and dp[0][j] = j (insert all of word2).
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
# Base cases
for i in range(m+1): dp[i][0] = i # delete all of word1
for j in range(n+1): dp[0][j] = j # insert all of word2
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] # no cost
else:
dp[i][j] = 1 + min(
dp[i][j-1], # insert
dp[i-1][j], # delete
dp[i-1][j-1] # replace
)
return dp[m][n]
print(edit_distance('horse', 'ros')) # 3
print(edit_distance('intention', 'execution')) # 5Understanding the Three Operations
The three operations map directly to moves in the DP table: Replace dp[i-1][j-1]+1 — we matched both characters but paid one cost. Delete from word1 dp[i-1][j]+1 — remove a character from word1 (move up in the table). Insert into word1 dp[i][j-1]+1 — insert a character to match word2 (move left). The minimum of the three gives the optimal edit path.
# Visualise the DP table for 'cat' → 'cut'
# dp[i][j] = min edits for word1[:i] vs word2[:j]
word1, word2 = 'cat', 'cut'
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i
for j in range(n+1): dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1]==word2[j-1]: dp[i][j]=dp[i-1][j-1]
else: dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
print(' ', ' '.join(' '+word2))
for i, row in enumerate(dp):
print((' ' if i==0 else word1[i-1]), row)Space Optimisation to O(n)
Edit distance only needs the current row and the previous row. Use a 1D array of size n+1 and track the diagonal value (dp[i-1][j-1]) separately before each cell update. Process left to right: temp = dp[j] (old value = dp[i-1][j]), update dp[j] using dp[j] (delete), dp[j-1] (insert), and diagonal (replace).
def edit_distance_1d(word1, word2):
m, n = len(word1), len(word2)
dp = list(range(n + 1)) # initial row: 0,1,2,...,n
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0]
dp[0] = i # dp[i][0] = i
for j in range(1, n + 1):
temp = dp[j] # dp[i-1][j] before overwrite
if word1[i-1] == word2[j-1]:
dp[j] = diag
else:
dp[j] = 1 + min(dp[j], # delete
dp[j-1], # insert
diag) # replace
diag = temp
return dp[n]
print(edit_distance_1d('horse', 'ros')) # 3
print(edit_distance_1d('intention', 'execution')) # 5Reconstructing the Edit Operations
To reconstruct the actual sequence of edits, backtrack through the DP table from (m, n). At each cell: if word1[i-1] == word2[j-1], move diagonally (no operation). Otherwise, find which of the three neighbours gave the minimum and record the corresponding operation. This produces the edit script in reverse; reverse it for the final answer.
def edit_ops(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0]=i
for j in range(n+1): dp[0][j]=j
for i in range(1,m+1):
for j in range(1,n+1):
if word1[i-1]==word2[j-1]: dp[i][j]=dp[i-1][j-1]
else: dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
ops, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and word1[i-1]==word2[j-1]:
i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]<=dp[i-1][j] and dp[i][j-1]<=dp[i-1][j-1]):
ops.append(f'Insert {word2[j-1]} at pos {i}'); j-=1
elif i>0 and (j==0 or dp[i-1][j]<=dp[i][j-1] and dp[i-1][j]<=dp[i-1][j-1]):
ops.append(f'Delete {word1[i-1]} at pos {i-1}'); i-=1
else:
ops.append(f'Replace {word1[i-1]} with {word2[j-1]}'); i-=1; j-=1
return list(reversed(ops))
for op in edit_ops('horse', 'ros'): print(op)One-Edit Distance Check
A simpler interview problem: are two strings exactly one edit apart? This is O(n) without DP. Walk both strings simultaneously. On a mismatch, try all three operations (skip a char in s1, skip in s2, skip both) and check if the remainders are identical. If two mismatches occur, return False. This greedy approach avoids the full O(mn) DP when you only need to know if distance ≤ 1.
def is_one_edit_distance(s, t):
m, n = len(s), len(t)
if abs(m - n) > 1: return False
if m > n: return is_one_edit_distance(t, s) # ensure m <= n
for i in range(m):
if s[i] != t[i]:
if m == n:
return s[i+1:] == t[i+1:] # replace
else:
return s[i:] == t[i+1:] # insert into s (delete from t)
return m + 1 == n # all matched, lengths differ by 1
print(is_one_edit_distance('ab', 'acb')) # True (insert c)
print(is_one_edit_distance('ab', 'ab')) # False (zero edits)
print(is_one_edit_distance('ab', 'abc')) # True (append c)
print(is_one_edit_distance('ab', 'xyz')) # FalseEdit Distance vs LCS Comparison
Edit distance (with all three ops) and LCS are complementary views of string similarity. Edit distance counts difference; LCS counts similarity. When only insertions and deletions are allowed (no replace), edit distance = m + n - 2×LCS. When substitutions are allowed, the DP is slightly different: the diagonal contributes dp[i-1][j-1] on match (free) or dp[i-1][j-1]+1 on replace. Both algorithms run in O(mn) time.
def lcs_len(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
return dp[m][n]
def edit_insert_delete_only(s1, s2):
return len(s1) + len(s2) - 2 * lcs_len(s1, s2)
print(edit_insert_delete_only('sea', 'eat')) # 2
print(edit_distance('sea', 'eat')) # 2 (same here: replace not needed)Fuzzy String Matching
Edit distance powers real-world fuzzy matching. A spell-checker suggests corrections within edit distance 1 or 2 of the typed word. The challenge at scale is avoiding O(mn × dict_size) comparisons. Solutions include BK-trees (a metric tree for edit distance), n-gram indexing, and approximate string matching algorithms like Bitap. Understanding the underlying DP helps you reason about the efficiency of these higher-level tools.
def spell_suggest(typed, dictionary, max_dist=2):
'''Return words in dictionary within max_dist edits of typed.'''
suggestions = []
for word in dictionary:
if abs(len(typed) - len(word)) <= max_dist:
if edit_distance(typed, word) <= max_dist:
suggestions.append(word)
return suggestions
def edit_distance(w1, w2):
dp = list(range(len(w2)+1))
for i,c1 in enumerate(w1,1):
prev = i
for j,c2 in enumerate(w2,1):
temp = dp[j]
dp[j] = prev if c1==c2 else 1+min(dp[j],prev,dp[j-1])
prev = temp
return dp[len(w2)]
dictionary = ['horse', 'worse', 'house', 'morse', 'nurse']
print(spell_suggest('harse', dictionary)) # horse, worse, house, morseWeighted Edit Distance
In some applications, different operations have different costs. For example, transposing adjacent characters (common typo) might cost less than a full replacement. The Damerau-Levenshtein distance adds transposition as a fourth operation. The DP extends to: also check dp[i-2][j-2]+1 when word1[i-1]==word2[j-2] and word1[i-2]==word2[j-1]. This more accurately models keyboard typos.
def damerau_levenshtein(s, t):
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0]=i
for j in range(n+1): dp[0][j]=j
for i in range(1,m+1):
for j in range(1,n+1):
cost = 0 if s[i-1]==t[j-1] else 1
dp[i][j] = min(
dp[i-1][j]+1, # delete
dp[i][j-1]+1, # insert
dp[i-1][j-1]+cost # replace
)
# Transposition
if i>1 and j>1 and s[i-1]==t[j-2] and s[i-2]==t[j-1]:
dp[i][j] = min(dp[i][j], dp[i-2][j-2]+1)
return dp[m][n]
print(damerau_levenshtein('CA', 'ABC')) # 2
print(damerau_levenshtein('ab', 'ba')) # 1 (transposition)DNA Sequence Alignment
Bioinformatics uses edit distance variants for DNA sequence alignment. The Needleman-Wunsch algorithm is a global alignment DP closely related to LCS and edit distance, where match gives +1, mismatch gives -1, and gap (insert/delete) gives a penalty. The Smith-Waterman variant performs local alignment (find the best-matching substring). Both are O(mn) DP algorithms with the same table-filling structure.
def needleman_wunsch(seq1, seq2, match=1, mismatch=-1, gap=-1):
m, n = len(seq1), len(seq2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i * gap
for j in range(n+1): dp[0][j] = j * gap
for i in range(1,m+1):
for j in range(1,n+1):
score = match if seq1[i-1]==seq2[j-1] else mismatch
dp[i][j] = max(
dp[i-1][j-1] + score, # align
dp[i-1][j] + gap, # gap in seq2
dp[i][j-1] + gap # gap in seq1
)
return dp[m][n]
print(needleman_wunsch('GATTACA', 'GCATGCU')) # alignment scoreInterview Approach for Edit Distance
When asked edit distance in an interview: (1) Confirm allowed operations (insert/delete/replace). (2) Define the DP state clearly. (3) Write out the three cases and the recurrence explicitly. (4) State base cases: dp[i][0]=i and dp[0][j]=j. (5) Mention the O(n) space optimisation. (6) If time permits, trace through a small example like 'cat'→'cut' (1 replace) to validate. The O(mn) time and O(mn) → O(n) space are the standard complexity bounds.
# Clean interview solution
def min_distance(word1, word2):
m, n = len(word1), len(word2)
# O(n) space with rolling row
dp = list(range(n + 1))
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0]
dp[0] = i
for j in range(1, n + 1):
temp = dp[j]
if word1[i-1] == word2[j-1]:
dp[j] = diag
else:
dp[j] = 1 + min(dp[j], dp[j-1], diag)
diag = temp
return dp[n]
# Time: O(mn), Space: O(n)
print(min_distance('horse', 'ros')) # 3
print(min_distance('intention', 'execution')) # 5
print(min_distance('', 'abc')) # 3
print(min_distance('abc', '')) # 3Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: edit distance dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+cost) with cost=0 on match else 1, base cases dp[i][0]=i and dp[0][j]=j represent transforming to/from an empty string, and the O(n) space optimisation uses a rolling 1D array with a diagonal variable. Next up we apply the same rolling-array trick to reduce 2D DP tables from O(mn) to O(min(m,n)) space.
Frequently asked questions
Is the “Edit Distance (Levenshtein)” lesson free?
Yes — the full text of “Edit Distance (Levenshtein)” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Edit Distance (Levenshtein)”?
Derive the edit-distance recurrence for insert/delete/replace operations and fill the DP table for pairs of strings of varying length. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Edit Distance (Levenshtein)” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Unique Paths and Minimum Path Sum on Grids
- Longest Common Subsequence
- Edit Distance (Levenshtein)
- Space Optimisation for 2D DP