Edit Distance (Levenshtein)

Medium

Find the minimum number of operations to transform one string into another.

📊 Complexity

Type	Value
Best	O(m×n)
Average	O(m×n)
Worst	O(m×n)
Space	O(m×n)

🏷️ Tags

DPString2D Table

📖 Introduction

Edit Distance (Levenshtein Distance) is the minimum number of operations needed to transform one string into another. Three operations are allowed: Insert, Delete, and Replace.

1/60

✏️Edit Distance

Transform "KITTEN" to "SITTING"? 3 operations allowed: • Insert: add a character • Delete: remove a character • Replace: change a character What's the minimum operations needed?

🔒

Edit Distance (Levenshtein)

Medium

Edit Distance (Levenshtein)

Find the minimum number of operations to transform one string into another.

📊 Complexity

Type	Value
Best	O(m×n)
Average	O(m×n)
Worst	O(m×n)
Space	O(m×n)

🏷️ Tags

DPString2D Table

📖 Introduction

Edit Distance (Levenshtein Distance) is the minimum number of operations needed to transform one string into another. Three operations are allowed: Insert, Delete, and Replace.

1/60

✏️Edit Distance

Transform "KITTEN" to "SITTING"? 3 operations allowed: • Insert: add a character • Delete: remove a character • Replace: change a character What's the minimum operations needed?

🔒

✏️Edit Distance