很那网站建设中国建设银行互联网网站首页
题目
给你两个单词 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 n1+n2;vector<vector<int>> dp(n1+1, vector<int>(n2+1));for(int i = 1; i < n1+1; i++){dp[i][0] = i;}for(int i = 1; i < n2+1; i++){dp[0][i] = i;}for(int i = 1; i < n1+1; i++){for(int j = 1; j < n2+1; 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];}
};