135. Edit Distance
Transform the source into the destination using insertions, deletions, and substitutions, each costing one. Equal character units can be matched without paying for an edit.
Swapping two neighboring characters is not a single permitted operation. Character-unit comparisons and empty-string boundaries follow the precise course contract.
Example 1
Input
a="horse", b="ros"
Output
3
Explanation: For example horse→rorse by substitution, rorse→rose by deleting the second r, then rose→ros by deleting e.
Example 2
Input
a="a", b="b"
Output
1
Explanation: One substitution is cheaper than delete plus insert.
Example 3
Input
a="ab", b="ba"
Output
2
Explanation: A swap is not one Levenshtein operation; two substitutions suffice.
Example 4
Input
a="", b="abc"
Output
3
Explanation: Insert the three code units.
Constraints
0 <= a.length, b.length <= 2000- Compare UTF-16 code units exactly, with case sensitivity.
Hints
Hint 1
Describe an optimum transforming two prefixes and calculate the empty-side costs.
Hint 2
What does the last alignment column consume for insert, delete, or substitute?
Hint 3
Save old dp[j] and old diagonal; current dp[j−1] is left. A matching pair costs zero.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Substitution competes with delete and insert
"ab"
"ac"
1