Harddynamic programmingstrings
Edit Distance
Count the fewest single-character edits that turn one word into another.
Return the minimum number of single-character edits needed to turn source into target.
The permitted edits are insert, delete and replace, each costing one.
Constraints
- 0 ≤ source.length, target.length ≤ 500
- Lowercase English letters only
Examples
- Input
- source = "horse", target = "ros"
- Output
- 3
- Input
- source = "intention", target = "execution"
- Output
- 5
- Input
- source = "same", target = "same"
- Output
- 0
- Why
- Nothing to do.
Submitting also runs 8 hidden tests.
Limits
2000 ms and 256 MB per test case.