Dynamic ProgrammingString2D DP
Find the minimum number of operations needed to turn one word into another. In one operation you may insert a character, delete a character, or replace a character.
Input
Line 1: the first word. Line 2: the second word. Both contain lowercase letters.
Output
Print the minimum number of operations.
Constraints
1 <= length of each word <= 200
Example 1
Input
horse ros
Output
3
horse -> rorse -> rose -> ros uses 3 operations.
Example 2
Input
intention execution
Output
5
Five operations are enough.