# My C++ code with comments, DP using an array [2][word1.size()+1]

• ``````class Solution {
public:
int minDistance(string word1, string word2) {
const int len1 = word1.size();
const int len2 = word2.size();

if(!len1 || !len2) return max(len1, len2); // one is an empty string, then just delete

int op[2][len1+1]; // work in ping-pong mode
int i, j, cur, next;

for(i=0;i<=len1;i++)  op[0][i]=i; // delete, op[0][i] means the number of op that make word1[0:i-1] match with word2[0:-1] (i.e.empty sub-string)

for(j=0; j<len2;j++)
{
cur = j%2; // ping-pong switch
next = 1 - cur;

// op[cur][i] is the number of op that make word1[0:i-1] match with word2[0:j-1]
// op[next][i] is the number of op that make word1[0:i-1] match with word2[0:j]
// if word1[i-1]==word2[j], then op[next][i] = op[cur][i-1];
// if word1[i-1]!=word2[j], then op[next][i] = min(op[cur][i-1] (i.e. replace),op[next][i-1] (delete), op[cur][i] (insert)) + 1;
op[next][0]= op[cur][0] + 1; //insert
for(i=1;i<=len1;i++)
{
if(word1[i-1]!=word2[j])
{
op[next][i] = min(op[cur][i-1], op[next][i-1]); // delete
op[next][i] = min(op[next][i], op[cur][i]) + 1; // insert
}
else
op[next][i] = op[cur][i-1];
}
}
return op[next][len1];

}
};``````

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