Faangprep Logo
Log inStart free
Browse curriculum

Edit Distance

Edit distance is the minimum number of operations (insert, delete, replace) required to convert one string into another.

READY

Ø

R

O

S

Ø

0
1
2
3

H

1
-
-
-

O

2
-
-
-

R

3
-
-
-

S

4
-
-
-

E

5
-
-
-

 

Initialize DP table. First row/col represent deletions/insertions from empty string.

Next

Converting 'H' to 'R'. Comparing 'H' and 'R'

Word 1

Word 2

Intuition

Think of it as the "cost" to transform one word into another. If characters match, it costs nothing. If they differ, you pay a price for an operation (Insert, Delete, or Replace). We want to find the cheapest path involves checking all three possibilities at each step.

Concept

2D Dynamic Programming:

We define dp[i][j] as the edit distance between the first i characters of word1 and the first j characters of word2.

Recurrence Relation:

  • Match (word1[i] == word2[j]): dp[i-1][j-1] (No op needed).
  • Mismatch (word1[i] != word2[j]): 1 + min(Insert, Delete, Replace)
    • Insert: dp[i][j-1]
    • Delete: dp[i-1][j]
    • Replace: dp[i-1][j-1]

How it Works

Tabulation Algorithm:

  1. Initialize dp table of size (m+1) × (n+1).
  2. Base Cases: First row (transform to empty string) = j. First column (transform from empty string) = i.
  3. Iterate i from 1 to m, j from 1 to n.
  4. Apply recurrence relation.
  5. Result is dp[m][n].

Step-by-Step Breakdown

Visualizing the Table:

  • Diagonal Move (No Cost): Match found.
  • Diagonal Move (Cost 1): Replacement.
  • Left Move (Cost 1): Insertion.
  • Up Move (Cost 1): Deletion.

When to Use

Applications:

  • Spell checkers (Levenshtein distance).
  • DNA sequence alignment (mutation analysis).
  • Plagiarism detection.

When NOT to Use

  • Simple Matches: If only exact matches matter.
  • Restricted Ops: If only insertions/deletions allowed, it's simpler (related to LCS).

How to Identify

"Minimum operations to convert...", "Levenshtein distance".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Longest Increasing Subsequence

Next

Max Path Sum

Frequently Asked Questions

What is Levenshtein Distance?

The minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into another.

Complexity of Edit Distance?

The standard DP solution is O(M*N) time and space, where M and N are the lengths of the two strings.

Real-world applications?

Auto-correct features, DNA sequencing, natural language processing (NLP), and plagiarism detection.