Edit Distance
Edit Distance
Edit distance (Levenshtein distance) measures the minimum number of single-character operations needed to transform one string into another. It is widely used in spell checking, DNA sequence alignment, and natural language processing for measuring string similarity.
Given two strings s1 and s2, compute the minimum edit distance using three operations: insert, delete, and replace (each with cost 1).
Algorithm
-
Create a (m+1) x (n+1) DP table where m and n are the lengths of s1 and s2. Initialize the first row and column with incremental values (base cases for empty string).
-
If the characters match, no operation is needed:
- Otherwise, take the minimum of insert, delete, or replace:
Where dp[i-1][j] is delete, dp[i][j-1] is insert, and dp[i-1][j-1] is replace.
Examples
Input:
s1 = "kitten", s2 = "sitting"
Output:
3
Three operations: replace k with s, replace e with i, insert g at the end. kitten -> sitten -> sittin -> sitting.
Input:
s1 = "horse", s2 = "ros"
Output:
3
Three operations: replace h with r, delete o, delete e. horse -> rorse -> rose -> ros.
Hint 1
Initialize dp[i][0] = i (deleting all of s1) and dp[0][j] = j (inserting all of s2). Then fill the table row by row: if characters match, copy the diagonal; otherwise, take 1 + min of three neighbors.
Hint 2
The three neighbors represent: dp[i-1][j] + 1 (delete from s1), dp[i][j-1] + 1 (insert into s1), dp[i-1][j-1] + 1 (replace). If s1[i-1] == s2[j-1], use dp[i-1][j-1] + 0 instead.
Requirements
- Compute the minimum number of single-character operations to transform s1 into s2
- Allowed operations: insert, delete, or replace a character (each costs 1)
- Handle empty strings (distance from empty to a string of length n is n)
- Return the edit distance as an integer
Constraints
- s1 and s2 can be empty strings
- String lengths are at most 1000
- Return a non-negative integer
- Time limit: 300 ms
Try Similar Problems
Log in to take notes on this problem
Accepts: string
Accepts: string
Edit Distance
Edit Distance
Edit distance (Levenshtein distance) measures the minimum number of single-character operations needed to transform one string into another. It is widely used in spell checking, DNA sequence alignment, and natural language processing for measuring string similarity.
Given two strings s1 and s2, compute the minimum edit distance using three operations: insert, delete, and replace (each with cost 1).
Algorithm
-
Create a (m+1) x (n+1) DP table where m and n are the lengths of s1 and s2. Initialize the first row and column with incremental values (base cases for empty string).
-
If the characters match, no operation is needed:
- Otherwise, take the minimum of insert, delete, or replace:
Where dp[i-1][j] is delete, dp[i][j-1] is insert, and dp[i-1][j-1] is replace.
Examples
Input:
s1 = "kitten", s2 = "sitting"
Output:
3
Three operations: replace k with s, replace e with i, insert g at the end. kitten -> sitten -> sittin -> sitting.
Input:
s1 = "horse", s2 = "ros"
Output:
3
Three operations: replace h with r, delete o, delete e. horse -> rorse -> rose -> ros.
Hint 1
Initialize dp[i][0] = i (deleting all of s1) and dp[0][j] = j (inserting all of s2). Then fill the table row by row: if characters match, copy the diagonal; otherwise, take 1 + min of three neighbors.
Hint 2
The three neighbors represent: dp[i-1][j] + 1 (delete from s1), dp[i][j-1] + 1 (insert into s1), dp[i-1][j-1] + 1 (replace). If s1[i-1] == s2[j-1], use dp[i-1][j-1] + 0 instead.
Requirements
- Compute the minimum number of single-character operations to transform s1 into s2
- Allowed operations: insert, delete, or replace a character (each costs 1)
- Handle empty strings (distance from empty to a string of length n is n)
- Return the edit distance as an integer
Constraints
- s1 and s2 can be empty strings
- String lengths are at most 1000
- Return a non-negative integer
- Time limit: 300 ms
Try Similar Problems
Log in to take notes on this problem
Accepts: string
Accepts: string