119 · edit distance

describe

Give two words word1 and word2, Work out what will be word1 Convert to word2 The minimum number of operations .
You can perform three operations ：

• Insert a character
• Delete a character
• Replace a character

---

Wechat plus jiuzhang15 Send verification information 【 Big factories in China 】 Collar byte 、 Ali 、 Baidu and other latest high-frequency questions

len(word1),len(word2)<=500len(word1), len(word2) <= 500len(word1),len(word2)<=500

Examples

Examples 1：

Input ：

word1 = "horse"
word2 = "ros"

Output ：

3

explain ：

horse -> rorse ( Replace 'h' by 'r')
rorse -> rose ( Delete 'r')
rose -> ros ( Delete 'e')

Examples 2：

Input ：

word1 = "intention"
word2 = "execution"

Output ：

5

explain ：

intention -> inention ( Delete 't')
inention -> enention ( Replace 'i' by 'e')
enention -> exention ( Replace 'n' by 'x')
exention -> exection ( Replace 'n' by 'c')
exection -> execution ( Insert 'u')

int dp4(string word1, int s1, string word2, int s2, map<vector<int>, int> &memo)
{

    if (s2 >= word2.size())
    {
        int tmp = word1.size() - s1;
        tmp = tmp > 0 ? tmp : 0;
        return tmp;  // Delete the remaining
    }
    if (s1 >= word1.size())
    {  // Insert remaining
        int tmp = word2.size() - s2;
        tmp = tmp > 0 ? tmp : 0;

        return tmp;
    }

    vector<int>vec = { s1,s2 };

    auto it = memo.find(vec);
    if (it != memo.end())
    {
        return it->second;
    }

    if (word1[s1] == word2[s2])
    {
        memo[vec] = dp4(word1, s1+ 1, word2, s2 + 1, memo);
    }
    else
    {
        // Insert... Respectively , Delete , Replace
        int insetCount = 1 + dp4(word1, s1, word2, s2 + 1, memo);// Insert
        int deleteCount = 1 + dp4(word1, s1 + 1, word2, s2, memo); // Delete
        int replaceCount = 1 + dp4(word1, s1 + 1, word2, s2 + 1, memo); // Replace
        int tmpMin = min(insetCount, deleteCount);
        memo[vec] = min(tmpMin, replaceCount);
    }
    return     memo[vec];
}

int minDistance(string word1, string word2) {
    map<vector<int>, int> memo;
    return dp4(word1, 0, word2, 0,memo);
}