# Share my C++ solution,easy to understand

• https://en.wikipedia.org/wiki/Edit_distance

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

if (len1 == 0)
return len2;
if (len2 == 0)
return len1;

int dp[len1+1][len2+1];

for (int i = 0; i <= len2; i++)
dp[0][i] = i;

for (int i = 0; i <= len1; i++)
dp[i][0] = i;

for (int row = 1; row <= len1; row++)
{
for (int col = 1; col <= len2; col++)
{
dp[row][col] = min(dp[row][col - 1], dp[row - 1][col]) + 1;

if (word1[row-1] == word2[col-1])
dp[row][col] = min(dp[row][col], dp[row-1][col-1]);
else
dp[row][col] = min(dp[row][col], dp[row-1][col-1] + 1);
}
}

return dp[len1][len2];
}
};
``````

• Optimization in Space Complexity:

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

if (len1 == 0)
return len2;
if (len2 == 0)
return len1;

len1++;
len2++;
int dp_pre[len2];
int dp_cur[len2];

for (int i = 0; i < len2; i++)
dp_pre[i] = i;

for (int row = 1; row < len1; row++)
{
dp_cur[0] = row;

for (int col = 1; col < len2; col++)
{
dp_cur[col] = min(dp_cur[col-1], dp_pre[col]) + 1;
dp_cur[col] = min(dp_cur[col], dp_pre[col-1] + (word1[row-1] == word2[col-1] ? 0 : 1));
}

for (int k = 0; k < len2; k++)
dp_pre[k] = dp_cur[k];
}

return dp_cur[len2-1];
}
};``````

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