Loading...
Loading...
Loading...
You may insert one letter, delete one letter or replace one letter in a word. Given a word A and a word B, print the smallest number of edits that turns A into B.
Example 1
Input
kitten sitting
Output
3
Replace k with s, replace e with i, insert g.
Example 2
Input
horse ros
Output
3
Try the problem first. Open one hint at a time.
Let dp[i][j] be the edits for the first i letters of A and the first j letters of B.
Equal letters copy the diagonal. Otherwise add 1 to the smallest of above, left and diagonal.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor