class Solution {
private:
int d[][];
public:
int minDistance(string word1, string word2)
{
int len1 = word1.length();
int len2 = word2.length();
for(int i=;i<=len1;i++)
d[i][]= i;
for(int j=;j<=len2;j++)
d[][j]=j;
for(int i=;i <=len1;i++)
{
for(int j=;j<=len2;j++)
{
int diff;
if(word1[i-] == word2[j-])
diff = ;
else
diff = ;
int temp = min(d[i-][j] + , d[i][j-] + );
d[i][j] = min(temp, d[i-][j-] + diff);
}
}
return d[len1][len2];
}
};
这是《趣学算法》一书中4-4节提供的代码，在leetcode上运行，速度比较慢，392ms（5.16%），12.9mb（5.22%）。
补充一个python的实现：
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m = len(word1)
n = len(word2)
dp = [[ for _ in range(n+)]for _ in range(m+)]
for j in range(n+):
dp[][j] = j
for i in range(m+):
dp[i][] = i
for i in range(,m+):
for j in range(,n+):
diff = if word1[i-] != word2[j-] else
minval = min(dp[i-][j]+,dp[i][j-]+)
minval = min(minval,dp[i-][j-]+diff)
dp[i][j] = minval
return dp[m][n]
240ms，16.4mb
下面提供leetcode中一个12ms，8.5mb的解决方案：
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.length();
int n = word2.length();
vector<int> dp(m+, );
int i, j;
int temp, min;
for(i=;i<=m;i++)
dp[i] = i;
for(j=;j<=n;j++)
{
temp = dp[];
dp[]++;
for(i=;i<=m;i++)
{
min = temp + (word1[i-]!=word2[j-]);
min = (dp[i-]+)<min?(dp[i-]+):min;
min = (dp[i]+)<min?(dp[i]+):min;
temp = dp[i];
dp[i] = min;
}
}
return dp[m];
}
};
将第二种写法，转化为python语法：
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m = len(word1)
n = len(word2)
dp = list(range(m+))
for j in range(,n+):
temp = dp[]
dp[] +=
for i in range(,m+):
diff = if word1[i-] != word2[j-] else
minval = temp + diff
minval = min(minval,dp[i-]+)
minval = min(minval,dp[i]+)
temp = dp[i]
dp[i] = minval
return dp[m]
204ms，12.9mb