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:

a) Insert a character

b) Delete a character

c) Replace a character

**Thoughts:**

First, we explain the recursive structure here. Denote as the edit distance between and . For base case, we have:

Then, for the recursive step, we have:

- if since we don’t need to anything from to .
- if . Here we compare three options:
- Replace ch1 with ch2, hence .
- Insert ch2 into , hence .
- Delete ch1 from , hence .

**Code (Java):**

public class Solution {
public int minDistance(String word1, String word2) {
int[][] table = new int[word1.length()+1][word2.length()+1];
for(int i = 0; i < table.length; ++i) {
for(int j = 0; j < table[i].length; ++j) {
if(i == 0)
table[i][j] = j;
else if(j == 0)
table[i][j] = i;
else {
if(word1.charAt(i-1) == word2.charAt(j-1))
table[i][j] = table[i-1][j-1];
else
table[i][j] = 1 + Math.min(Math.min(table[i-1][j-1],
table[i-1][j]), table[i][j-1]);
}
}
}
return table[word1.length()][word2.length()];
}
}

**Code (C++):**

class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int> > table(word1.size()+1, vector<int>(word2.size()+1));
for(int i = 0; i < word1.size()+1; ++i) {
for(int j = 0; j < word2.size()+1; ++j) {
if(i == 0)
table[i][j] = j;
else if(j == 0)
table[i][j] = i;
else {
if(word1[i-1] == word2[j-1])
table[i][j] = table[i-1][j-1];
else
table[i][j] = min(min(1+table[i-1][j-1],
1+table[i-1][j]), 1+table[i][j-1]);
}
}
}
return table[word1.size()][word2.size()];
}
};

### Like this:

Like Loading...

*Related*