做网站推广托管注意,网站建设大概要多少钱,wordpress搭建的网站能干什么,会网站建设如何找工作72. 编辑距离
给你两个单词 word1 和 word2#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作#xff1a;
插入一个字符删除一个字符替换一个字符
示例 1#xff1a; 输入#xff1a;word1 “horse”, word2 “ros”…72. 编辑距离
给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符
示例 1 输入word1 “horse”, word2 “ros” 输出3 解释 horse - rorse (将 ‘h’ 替换为 ‘r’) rorse - rose (删除 ‘r’) rose - ros (删除 ‘e’)
示例 2 输入word1 “intention”, word2 “execution” 输出5 解释 intention - inention (删除 ‘t’) inention - enention (将 ‘i’ 替换为 ‘e’) enention - exention (将 ‘n’ 替换为 ‘x’) exention - exection (将 ‘n’ 替换为 ‘c’) exection - execution (插入 ‘u’)
提示 0 word1.length, word2.length 500 word1 和 word2 由小写英文字母组成
动态规划
dp[i][j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最近编辑距离为dp[i][j]。 这样定义的目的是便于初始化数组。
增加操作dp[i][j-1]1 删除操作dp[i-1][j]1 改操作dp[i-1][j-1]1
当word1[i-1]word2[j-1]时则dp[i][j]dp[i-1][j-1]无需操作
class Solution {
public:int dp[505][505];int minDistance(string word1, string word2) {int len1word1.size(),len2word2.size();//初始化数组操作for(int i0;ilen1;i) dp[i][0]i;for(int i0;ilen2;i) dp[0][i]i;for(int i1;ilen1;i){for(int j1;jlen2;j){if(word1[i-1]word2[j-1]) dp[i][j]dp[i-1][j-1];else dp[i][j]min(dp[i-1][j-1]1,min(dp[i-1][j]1,dp[i][j-1]1));}}return dp[len1][len2];}
};
