题目描述
给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
Example 1:
输入: “sea”, “eat” 输出: 2 解释: 第一步将”sea”变为”ea”，第二步将”eat”变为”ea”
Constraints:
- 给定单词的长度不超过500。
- 给定单词中的字符只含有小写字母。
解题思路
- 先找到两个字符串的最长公共子序列，保留公共的子序列
- 要想操作次数最少，其保留最长的即可。
C++代码
class Solution {
public:
int minDistance(string word1, string word2) {
int row = word1.size();
int col = word2.size();
vector<vector<int>> dp(row + 1, vector<int>(col + 1, 0));
for(int i = 1; i <= row; i++){
for(int j = 1; j <= col; j++){
if(word1[i - 1] == word2[j - 1]){
dp[i][j] = dp[i - 1][j - 1] + 1;
}else{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
int lcs = dp[row][col];
return word1.size() - lcs + word2.size() - lcs;
}
};
