网站备案名称填写规则,莱州做网站的公司,网站虚拟主持人,wordpress用户系统1. 题目
给你两个单词 s 和 t#xff0c;请你计算出将 s 转换成 t 所使用的最少操作数。
你可以对一个单词进行如下两种操作#xff1a;
删除一个字符替换一个字符
注意#xff1a; 不允许插入操作 题目保证有解
示例#xff1a;
输入#xff1a;s abcdefg请你计算出将 s 转换成 t 所使用的最少操作数。
你可以对一个单词进行如下两种操作
删除一个字符替换一个字符
注意 不允许插入操作 题目保证有解
示例
输入s abcdefg, t abdde
输出3提示
1 len(s), len(t) 200作者力扣 (LeetCode) 链接https://leetcode-cn.com/leetbook/read/high-frequency-algorithm-exercise/omxcgt/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。 2. 解题
类似题目LeetCode 72. 编辑距离DP
注意不能插入字符
class Solution {
public:int edit_distance(string s, string t) {int n1 s.size(), n2 t.size();vectorvectorint dp(n11, vectorint(n21, INT_MAX));for(int i 0; i n1; i)dp[i][0] i;//i个s字符变成0个t字符需要删除次数for(int i 0; i n2; i)dp[0][i] i;for(int i 1; i n1; i){for(int j 1; j n2; j){if(s[i-1] t[j-1])dp[i][j] dp[i-1][j-1];else{dp[i][j] dp[i-1][j-1]1;//替换s或t的字符if(i-1 j)//因为不能插入字符删除 s 的 i 字符前提是 s 字符串长度不能短于 t, 否则没有意义dp[i][j] min(dp[i][j], dp[i-1][j]1);if(j-1 i)//因为不能插入字符删除 t 的 j 字符前提是 t 字符串长度不能短于 s, 否则没有意义dp[i][j] min(dp[i][j], dp[i][j-1]1);}}}return dp[n1][n2];}
};36 ms 13.2MB C
