Question
The Story of Two Words
In the Land of Letters, there were two words — word1 and word2. Long ago, they were the same, but over time, extra letters made them different.
A young scribe now has the task to make them identical again.
In one step, the scribe can delete one letter from either word.
Your goal is to find the minimum number of deletions needed to make both words the same.
Input
The first line of the input contains a string representing word1.
The second line of the input contains a string representing word2.
The second line of the input contains a string representing word2.
Output
Print the minimum number of steps required to make word1 and word2 identical.
Example
Input:
sea
eat
Output:
2
Explanation:
You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Input:
newton
wt
Output:
4
sea
eat
Output:
2
Explanation:
You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Input:
newton
wt
Output:
4