基本上是抄的，记录下代码。。。
class Solution {
public:
int minDistance(string word1, string word2) {
if(word1.size()==0||word2.size()==0) return word2.size()!=0?word2.size():word1.size();
size_t m = word1.size(),n=word2.size();
vector<vector<int>> table(m+1,vector<int>(n+1,0));
vector<int>(n+1,0).swap(table[0]);
for(auto i=1;i<=m;i++)
{
table[i][0]=i;
}
for(auto i=1;i<=n;i++)
{
table[0][i]=i;
}
for(auto i=1;i<=m;i++)
{
for(auto j=1;j<=n;j++)
{
auto ii=i-1,jj=j-1;
table[i][j] = min({(word1[ii]==word2[jj]?0:1)+table[ii][jj],table[ii][j]+1,table[i][jj]+1});
}
}
return table[m][n];
}
};
主要分析一下转移方程，把它记下来
auto ii=i-1,jj=j-1;
table[i][j] = min({(word1[ii]==word2[jj]?0:1)+table[ii][jj],table[ii][j]+1,table[i][jj]+1});
状态表中的数字table[i][j]代表word1中的前i个字符匹配至字符串的前j个字符所需要的最小步数。
这里的状态转移分三种情况
- 字符匹配
- 字符替换
- 字符删除
- 字符插入
其中字符串匹配和字符串替换的情况均从table[i-1][j-1]转换而来，若table[i]与table[j]相同,则不需要进行字符串替换table[i][j]=table[i-1][j-1]，若其不同，则需要进行一次字符串替换,table[i][j]=table[i-1][j-1]+1,其组成转移方程的前半段。
(word1[ii]==word2[jj]?0:1)+table[ii][jj]
字符删除的情况则从table[i][j-1]'匹配转移而来，程序直接选择删除word1中的一个字符以维持之前的匹配结果，即table[i][jj]+1字符插入的情况则是程序选择向当前位置插入一个字符以完成匹配，即table[i][j]+1`
三种转移的情况下取最小即为转移方程。
