Deletion of two strings

Given word1 and word2, find the minimum steps required to make word1 and word2 the same, each step can delete a character in any string.

Example

Example 1:

Input: "sea" and "eat"
Output: 2
 Explanation: Step 1 needs to change "sea" into "ea" and step 2 needs to change "eat" into "ea".

Example 2:

Input: "horse", "ros"
Output: 4
 Explanation: It takes three steps to make "horse" an "os", and one step to make "ros" an "os".

Matters needing attention

The length of the given word will not exceed 500.
The given words contain only lowercase letters.

How does input test data (one parameter per row) understand test data?

 

class Solution {
public:
    /**
     * @param word1: a string
     * @param word2: a string
     * @return: return a integer
     */
    map<pair<int,int>, int> mymap;
    int minDistance(string &word1, string &word2) {
        // write your code here
        return dp(word1,word2, word1.size()-1,word2.size()-1);
    }
    
    
    int dp(string &word1, string &word2,int x, int y)
    {
        if(mymap.count(make_pair(x,y)) != 0)
        {
            return mymap[make_pair(x,y)];
        }
        if(x == 0 && y == 0 && word1[x] == word2[y])
            return 0;
        if(x == 0 && y == 0 && word1[x] != word2[y])
        {
            return 2;
        }
        if(x < 0 && y < 0)
            return 0;
        if(x < 0)
        {
            return y+1;     
        }
        if(y < 0)
            return x+1;
        if(word1[x] == word2[y])
        {
            return dp(word1,word2,x-1,y-1);
        }
        
        int time1 = dp(word1,word2,x,y-1);
        mymap[make_pair(x,y-1)] = time1;
        int time2 = dp(word1,word2,x-1,y);
        mymap[make_pair(x-1,y)] = time2;
        int ret = min(time1, time2)+1;
        mymap[make_pair(x,y)] = ret;
        return ret;
    }
};

 

Posted on Sun, 06 Oct 2019 03:47:52 -0700 by pjleonhardt