问题
给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符
示例 1:
输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
分析
f[i][j]表示s1的前i个字符变成s2的前j个字符最少操作数,以s1视角,添加:f[i][j] = f[i][j-1]+1;删除:f[i][j] = f[i-1][j]+1;替换:f[i][j] = f[i-1][j-1] + 1。如果当前比较的两个字符相等,s1[i-1] == s2[j-1],有 dp[i][j] = dp[i-1][j-1].
代码
class Solution {
public:string s1, s2;int n1, n2;static const int N = 5e2+10;int f[N][N]; // f[i][j]表示s1的前i个字符变成s2的前j个字符最少操作数int minDistance(string word1, string word2) {this->s1 = word1, this->s2 = word2;n1 = word1.size(); n2 = word2.size();for (int i = 0; i <= n1; i++) {f[i][0] = i; // s1的前i个字符变为空串}for (int i = 0; i <= n2; i++) {f[0][i] = i;}// 在s1 insert相当于在s2 deletefor (int i = 1; i <= n1; i++) {for (int j = 1; j <= n2; j++) {if (s1[i-1] != s2[j-1]) {f[i][j] = min(min(f[i-1][j]+1, f[i][j-1]+1), f[i-1][j-1]+1);} else {f[i][j] = f[i-1][j-1];}}}return f[n1][n2];}
};