## Dynamic programing for edit distance (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:
a) Insert a character
b) Delete a character
c) Replace a character

Thoughts:
First, we explain the recursive structure here. Denote $ed(s_{1}, s_{2})$ as the edit distance between $s_{1}$ and $s_{2}$. For base case, we have:

• $ed('', '') = 0$
• $ed('', s) = ed(s, '') = \|s\|$

Then, for the recursive step, we have:

• $ed(s_{1}+ch1, s_{2}+ch2) = ed(s_{1}, s_{2})$ if $ch1 == ch2$ since we don’t need to anything from $s_{1},s_{2}$ to $s_{1}+ch1, s_{2}+ch2$.
• $ed(s_{1}+ch1, s_{2}+ch2) = \min(1 + ed(s_{1}, s_{2}), 1 + ed(s_{1}+ch1, s_{2}), 1 + ed(s_{1}, s_{2}+ch2))$ if $ch1 != ch2$. Here we compare three options:
1. Replace ch1 with ch2, hence $1 + ed(s_{1}, s_{2})$.
2. Insert ch2 into $s_{2}$, hence $1 + ed(s_{1}+ch1, s_{2})$.
3. Delete ch1 from $s_{1}$, hence $1 + ed(s_{1}, s_{2}+ch2)$.

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()];
}
};

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2de90405484', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2de904054cb',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2de904054ce',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});