799. Edit Steps
A spell-checker repairs a mistyped word one keystroke at a time. In a single step it may insert one character at any position, delete one character, or replace one character by a different one. Steps are applied one after another, so each step works on the result of the previous one.
Given the typed word a and the intended word b, return the minimum number of steps needed to turn a into b. Two identical words need 0 steps.
Aim for O(n*m) time, where n and m are the lengths of the words, and O(min(n, m)) extra space.
Example 1
- Input:
- a = "lanternfish", b = "landfill"
- Output:
- 6
- Explanation:
The minimum number of single-character steps to turn "lanternfish" into "landfill" is 6.
Example 2
- Input:
- a = "owlowl", b = "wolwol"
- Output:
- 4
- Explanation:
The minimum number of single-character steps to turn "owlowl" into "wolwol" is 4.
Example 3
- Input:
- a = "ninja", b = "jinx"
- Output:
- 3
- Explanation:
The minimum number of single-character steps to turn "ninja" into "jinx" is 3.
Constraints
1 ≤ a.length, b.length ≤ 1000
Both words contain only lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n*m)
- Space
- O(min(n,m))