# Share my DP Solution

• `T[i][j]` represents the minimum steps `w1[:i]` needs to transform to `w2[:j]`.

1. 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
``````
1. 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];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.