网站后台维护系统,html做网站,wordpress中文版安装教程 pdf,巨野县建设局网站给你两个单词 word1 和 word2#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作#xff1a;
插入一个字符删除一个字符替换一个字符 输入#xff1a;word1 “horse”, word2 “ros” 输出#xff1a;3 解释#xff1a…给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符 输入word1 “horse”, word2 “ros” 输出3 解释 horse - rorse (将 ‘h’ 替换为 ‘r’) rorse - rose (删除 ‘r’) rose - ros (删除 ‘e’) 原题链接https://leetcode.cn/problems/edit-distance/
思路
以 dp[i][j] 表示 word1[0: i]、word2[0: j] 的编辑距离。
转移方程 当 word1[i] word2[j] 时此时无需操作dp[i][j] dp[i-1][j-1] 当 word1[i] ! word2[j] 时dp[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 1 这里 dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 三项分别代表 替换、删除、增加。
边界条件 当 i 0 或 j 0 时显然 dp[i][0] 或 dp[0][j] 等于另一个子字符串的长度。即 dp[i][0] i 、dp[0][j] j
代码
class Solution {
public:int minDistance(string word1, string word2) {// if word1[i] word2[j], dp[i][j] dp[i-1][j-1]// else: dp[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 1int m word1.size();int n word2.size();vectorvectorint dp(m1, vectorint (n1, 0));for (int i 0; i m; i) {dp[i][0] i;}for (int j 0; j n; j) {dp[0][j] j;}for (int i 1; i m; i) {for (int j 1; j n; j) {if (word1[i-1] word2[j-1]) {dp[i][j] dp[i-1][j-1];} else {dp[i][j] min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) 1;}}}return dp[m][n];}
};
