Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Edit Distance

Dynamic Programminghard

Implement `minDistance(a, b)` returning the minimum number of single-character insertions, deletions, or replacements to turn `a` into `b`.

Sample tests

Input: minDistance("horse", "ros")
Output: 3
Input: minDistance("intention", "execution")
Output: 5

+ 1 hidden test run on Submit.

Hints

Common pitfalls
  • Forgetting the base cases for transforming to or from an empty string.

Learning resources

  • Wikipedia: Dynamic programming
Approach & explanation (try first)

Levenshtein DP over prefixes computes edit distance in O(m * n) time.

Loading...
⌘/Ctrl + Enter

Run your code to see results.