Loading...
Loading...
Loading...
The library app matches the name a student types against the name in the college register. To judge how close the typed name is, it counts the fewest single-letter changes that turn the typed name into the registered name.
One change is one of these: insert a letter anywhere, delete a letter, or replace a letter with another letter.
Print the fewest changes needed. The typed name may be empty, shown as an empty first line.
Example 1
Input
kiran karan
Output
1
Replace the i with an a: one change.
Example 2
Input
sunil sunita
Output
2
Replace the l with a t, then insert an a at the end: two changes.
Try the problem first. Open one hint at a time.
Look at the last letters of both names. If they are equal, they need no change, and the answer is the same as without them.
If they differ, the last change is one of three: replace the last typed letter, delete it, or insert the last registered letter. Try all three.
Let dist[i][j] be the answer for the first i typed letters and the first j registered letters. Turning i letters into nothing takes i deletes, and nothing into j letters takes j inserts.
Fill the table row by row; each cell needs the cell above, the cell on the left and the cell diagonally up-left.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor