扁平化企业网源码win8风格精简化源码asp带后台企业网站,宜宾 网站建设,做网站销售电话术语,深圳定制建站题目
给你两个单词 w o r d 1 word1 word1 和 w o r d 2 word2 word2#xff0c; 请返回将 w o r d 1 word1 word1 转换成 w o r d 2 word2 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作#xff1a;
插入一个字符删除一个字符替换一个字符
方法—动…题目
给你两个单词 w o r d 1 word1 word1 和 w o r d 2 word2 word2 请返回将 w o r d 1 word1 word1 转换成 w o r d 2 word2 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符
方法—动态规划
定义 d p dp dp 数组 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示 w o r d 1 [ 0... i − 1 ] word1[0...i-1] word1[0...i−1] 与 w o r d 2 [ 0... j − 1 ] word2[0...j-1] word2[0...j−1] 的编辑距离边界条件 d p [ 0 ] [ j ] j , d p [ i ] [ 0 ] i dp[0][j] j, dp[i][0] i dp[0][j]j,dp[i][0]i转移 若 w o r d 1 [ i − 1 ] w o r d [ j − 1 ] word1[i-1] word[j-1] word1[i−1]word[j−1] d p [ i ] [ j ] m i n ( d p [ i − 1 ] [ j ] 1 , d p [ i ] [ j − 1 ] 1 , d p [ i ] [ j ] ) dp[i][j] min(dp[i-1][j]1,dp[i][j-1]1,dp[i][j]) dp[i][j]min(dp[i−1][j]1,dp[i][j−1]1,dp[i][j])若 w o r d 1 [ i − 1 ] ! w o r d [ j − 1 ] word1[i-1] ! word[j-1] word1[i−1]!word[j−1] d p [ i ] [ j ] m i n ( d p [ i − 1 ] [ j ] 1 , d p [ i ] [ j − 1 ] 1 , d p [ i ] [ j ] 1 ) dp[i][j] min(dp[i-1][j]1,dp[i][j-1]1,dp[i][j]1) dp[i][j]min(dp[i−1][j]1,dp[i][j−1]1,dp[i][j]1)
代码
class Solution {
public:int minDistance(string word1, string word2) {int n1 word1.size();int n2 word2.size();if(n1*n2 0)return n1n2;vectorvectorint dp(n11, vectorint(n21));for(int i 1; i n11; i){dp[i][0] i;}for(int i 1; i n21; i){dp[0][i] i;}for(int i 1; i n11; i){for(int j 1; j n21; j){if(word1[i-1] word2[j-1]){dp[i][j] min(dp[i-1][j]1, min(dp[i][j-1]1, dp[i-1][j-1]));}else{dp[i][j] min(dp[i-1][j]1, min(dp[i][j-1]1, dp[i-1][j-1]1));}}}return dp[n1][n2];}
};
