Lintcode: Edit Distance

Given two words word1 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", return 3.

Tags Expand 

String Dynamic Programming

Thought and codes:

http://www.cnblogs.com/springfor/p/3896167.html

Time: O(m*n)
Space: O(m*n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class Solution { public: /** * @param word1 & word2: Two string. * @return: The minimum number of steps. */ int minDistance(string word1, string word2) { // write your code herevect vector< vector<int> > dp(word1.size() + 1, vector<int>(word2.size() + 1)); dp[0][0] = 0; for(int i = 1; i <= word1.size(); i++){ dp[i][0] = i; } for(int i = 1; i <= word2.size(); i++){ dp[0][i] = i; } for(int i = 1; i <= word1.size(); i++){ for(int j = 1; j <= word2.size(); j++){ if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; else{ int replace = dp[i - 1][j - 1] + 1; int insert = dp[i][j - 1] + 1; int deletion = dp[i - 1][j] + 1; int m = min(insert, deletion); dp[i][j] = min(m, replace); } } } return dp[word1.size()][word2.size()]; } };