Problems

1 / 1

Edit Distance

NLP

Easy

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:

dp[i][j] = dp[i-1][j-1] \quad \text{if } s_1[i-1] = s_2[j-1]

Otherwise, take the minimum of insert, delete, or replace:

dp[i][j] = 1 + \min(dp[i-1][j],\; dp[i][j-1],\; dp[i-1][j-1])

Where dp[i-1][j] is delete, dp[i][j-1] is insert, and dp[i-1][j-1] is replace.

Return the minimum edit distance as an integer.

Loading visualization...

Examples

Input: s1 = "kitten", s2 = "sitting"

Output: 3

Explanation: Two replacements and one insertion transform kitten into sitting.

Input: s1 = "horse", s2 = "ros"

Output: 3

Hint 1

Initialize the first DP row and column with distances from an empty prefix.

Hint 2

Use the diagonal value for matching characters; otherwise add one to the minimum neighboring state.

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

Word Count Dict Bag Of Words Bigram Probabilities Text Chunking Remove Stopwords

Prev Next

Edit Distance

NLP

Easy

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:

dp[i][j] = dp[i-1][j-1] \quad \text{if } s_1[i-1] = s_2[j-1]

Otherwise, take the minimum of insert, delete, or replace:

dp[i][j] = 1 + \min(dp[i-1][j],\; dp[i][j-1],\; dp[i-1][j-1])

Where dp[i-1][j] is delete, dp[i][j-1] is insert, and dp[i-1][j-1] is replace.

Return the minimum edit distance as an integer.

Loading visualization...

Examples

Input: s1 = "kitten", s2 = "sitting"

Output: 3

Explanation: Two replacements and one insertion transform kitten into sitting.

Input: s1 = "horse", s2 = "ros"

Output: 3

Hint 1

Initialize the first DP row and column with distances from an empty prefix.

Hint 2

Use the diagonal value for matching characters; otherwise add one to the minimum neighboring state.

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

Word Count Dict Bag Of Words Bigram Probabilities Text Chunking Remove Stopwords

Case 1

Case 2

s1 =

Accepts: string

s2 =

Accepts: string

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:

dp[i][j] = dp[i-1][j-1] \quad \text{if } s_1[i-1] = s_2[j-1]

Otherwise, take the minimum of insert, delete, or replace:

dp[i][j] = 1 + \min(dp[i-1][j],\; dp[i][j-1],\; dp[i-1][j-1])

Where dp[i-1][j] is delete, dp[i][j-1] is insert, and dp[i-1][j-1] is replace.

Return the minimum edit distance as an integer.