`T[i][j]`

represents the minimum steps `w1[:i]`

needs to transform to `w2[:j]`

.

- First, we look the base case either w1's or w2's length is equal to 0. The minimum step must be the non-zero one's length (i.e., delete/add all its characters. ). So, we have:

```
T[i][0] = i; // w2.size() == 0
T[0][j] = j; // w1.size(0 == 0
```

- Next, we see the normal case.

a.`w1[i - 1] == w2[j - 1]`

means that we don't need to change any character at this moment, so`T[i][j] = T[i - 1][j - 1]`

.

b.`w1[i - 1] != w2[j - 1]`

means that we need to change 1 character plus the`min(T[i][j - 1], T[i - 1][j], T[i - 1][j - 1])`

.

```
class Solution {
public:
int minDistance(string w1, string w2) {
int l1 = w1.size(), l2 = w2.size();
// T[i][j]: the min step need change w1[:i] to w2[:j]
vector<vector<int> > T(l1 + 1, vector<int>(l2 + 1, 0));
// T[0][j] = j
for(int j = 0; j <= l2; j++)
T[0][j] = j;
// T[i][0] = i
for(int i = 0; i <= l1; i++)
T[i][0] = i;
for(int i = 1; i <= l1; i++) {
for(int j = 1; j <= l2; j++) {
// w1, w2 have the same end at i, j.
// then, T[i][j] = T[i - 1][j - 1]
if(w1[i-1] == w2[j-1]) T[i][j] = T[i - 1][j - 1];
// w1, w2 have different end at i, j.
else
T[i][j] = 1 + min(T[i - 1][j - 1], min(T[i - 1][j], T[i][j - 1]));
}
}
return T[l1][l2];
}
};
```