## EDIST - Edit distance

You are given two strings, A and B. Answer, what is the smallest number of operations you need to
transform A to B?

Operations are:

1. Delete one letter from one of strings
2. Insert one letter into one of strings
3. Replace one of letters from one of strings with another letter

### Input

T - number of test cases

For each test case:

• String A
• String B

Both strings will contain only uppercase characters and they won't be longer than 2000 characters.

There will be 10 test cases in data set.

### Output

For each test case, one line, minimum number of operations.

### Example

```Input:
1
FOOD
MONEY

Output:
4```

hide comments
 < Previous 1 2 3 4 5 6 7 8 9 10 11 Next > boominggem: 2023-01-13 17:46:53 non of the comments help us with the syntax of reading an empty line. untill i know it i'll just keep seeing these wa wa wa wa wa :) camlot_9889e: 2022-08-12 23:35:12 wa on every submissions Last edit: 2022-08-12 23:36:27 mamad_urmu: 2021-07-05 13:55:30 wagner fischer algorithm Waseem Ahmed: 2021-06-27 10:12:38 Got an AC with DP. A simple Edit Distance application of DP. However got AC with 9.3+ with C++. Not sure why. Tried all types of optimizations. Used vector for DP and the standard approach. But not sure why the high runtime when other users have managed 0.18. harshh3010: 2021-01-31 15:07:22 C++ users, take input using cin... getline gives WA tejasreddyk: 2021-01-16 14:36:30 AC in one go after reading concept in CLRS and one video. good start on a DP distructo: 2020-12-31 09:09:39 Careful with the case a=0 && b=0 nitish_verma26: 2020-12-17 20:43:39 Initially I used strings which gave WA. Taking char arrays instead resulted in accepted code. I didn't understand why so. anurag_mishra: 2020-11-28 20:34:38 pass string with reference to get AC in top-down approach wille_25: 2020-10-02 12:28:03 Last edit: 2021-05-16 18:04:11

 Added by: Mislav Balunović Date: 2010-02-28 Time limit: 15s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: NODEJS OBJC PERL6 SQLITE VB.NET Resource: Internet