Bob and his girlfriend
All submissions for this problem are available.
It is Bob's girlfriend's birthday today. He is very happy, so he has written a very special message to express his love for her.
Now there is this friend of Bob who is very jealous of him.
So, he messed up with his special birthday message. Bob has got little time to transform back the message by making some operations.
To do so he can :
1) Delete one letter from one of messages
2) Insert one letter into one of messages
3) Replace one of letters from one of messages with another letter
What is the smallest number of operations needed to get the original message back?
- The first line of the input contains an integer T denoting the number of test cases.
- Each test case contains two lines, first line contains the original message and the second line contains messed up message.
For each test case, print minimum number of operations needed.
- 1 ≤ T ≤ 50
- 1 ≤ Length of string A, B <= 2000
Input: 1 ILOVEYOU IHATEYOU Output: 3
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions