Given two wordsword1_and_word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

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

Have you met this question in a real interview?

Yes

Example

Given word1 ="mart"and word2 ="karma", return3.

class Solution {

public:

/\*\*

 \* @param word1 & word2: Two string.

 \* @return: The minimum number of steps.

 \*/

int minDistance\(string word1, string word2\) {

    // write your code here

    int len1 = word1.size\(\);

    int len2 = word2.size\(\);

    int f\[len1 + 1\]\[len2 + 1\];

    for \(int i = 0; i <= len1; ++i\) {

        f\[i\]\[0\] = i;

    }

    for \(int j = 0; j <= len2; ++j\) {

        f\[0\]\[j\] = j;

    }

    for \(int i = 1; i <= len1; ++i\) {

        for \(int j = 1; j <= len2; ++j\) {

            if \(word1\[i - 1\] == word2\[j - 1\]\) {

                f\[i\]\[j\] = f\[i - 1\]\[j - 1\];

            } else {

                f\[i\]\[j\] = min\(min\(f\[i - 1\]\[j - 1\], f\[i\]\[j - 1\]\), f\[i - 1\]\[j\]\) + 1;

            }

        }            

    }

    return f\[len1\]\[len2\];

}

};