## 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 > imkiller: 2018-03-25 16:37:47 Just a simple editDistance problem . solve using dp. No constraints problem. BestOfLuckForOthers. erfanesm: 2018-02-20 07:31:38 this problem can't be solve in this way : cout<< max(s.size(),t.size) - LCS.size(); S = abba , T = bcba; LCS = bba => LCS.size() = 2 so our output will be 4-3 = "1" it takes us 2_operations : 1. Delete "C" => to string S 2. Insert "A" => to string T Last edit: 2018-02-20 07:33:07 bradyawn: 2018-01-24 22:23:33 AC in one go!!! = Why I hate SPOJ community People should shut up about AC in one go and do actually challenging problems nveenjain: 2018-01-16 10:59:53 Pass strings through reference, costed TLE :( asifk1997: 2018-01-14 05:25:55 standard dp problem AC in one go!!! Last edit: 2018-01-14 06:54:23 imshreyas: 2017-12-26 11:44:54 For reference https://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/ ayushgupta1997: 2017-12-19 11:13:00 Note : 1. Do it yourself. 2.Can refer web/youtube. 3.Again code yourself implementing the logic 4.Dont forget to clear the buffer using cin.ignore() :p costed me 2WA kmkhan_014: 2017-11-27 20:20:24 Last edit: 2017-11-27 20:20:54 aaman007: 2017-09-16 19:12:14 I tried to solve it by finding LCS....the cout << max(s.length(),s1.length()) - LCS << endl; still got WA satyabrat35: 2017-08-29 10:34:47 Levenshtein distance ... :)

 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