# C++ standard solution

• ``````/*
dp[i][j] 代表从A[1...i]变换到B[1....j]需要的最少的步骤

可以分为三种几种情况进行讨论：
1、A[i]=B[j]， 则从A[1...i]变换到B[1...j]的步数 dp[i][j] = dp[i-1][j-1]
2 A[i] != B[j]:

(1) 在A[i]后插入一个字符ch（ch=B[j]），耗费一步，那么问题转换为 A[1...i] --> B[1...j-1]的转换了（dp[i][j] = dp[i][j-1] + 1）
如  asdfe --> asdert  当前A[i] = e， B[j]=t,在A[i]后插入一个t(asdeft --> asdert)，耗费一步，
则问题转换为 asdfe --> asder 变换的步骤了A[i] --> B[j-1]

(2) 将A[i]删除，耗费一步，则问题转换为A[i...i-1] -->B[1...j] 的转换了(dp[i][j] = dp[i-1][j] + 1)

(3) 将A[i]替换为B[j]，耗费一步， 则问题转换为 A[1...i-1] --> B[1...j-1]的转换了(dp[i][j] = dp[i-1][j-1] + 1)

最后取三种转换的方式中步数最小的那种方案： dp[i+1][j+1] = min( min(dp[i+1][j]+1, dp[i][j+1]+1), dp[i][j]+1)

*/

class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
if(m==0 || n==0 )return max(m,n);
int dp[m+1][n+1];
for(int i=0; i<=m; i++)  dp[i][0] = i;
for(int i=0; i<=n; i++)  dp[0][i] = i;
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
if(word1[i] == word2[j]) dp[i+1][j+1] = dp[i][j];
else dp[i+1][j+1] = min( min(dp[i+1][j]+1, dp[i][j+1]+1), dp[i][j]+1);
}
}
return dp[m][n];
}
};``````

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