Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
思路:普通的DP很好写,问题是路径压缩的DP压缩如果进行,空间如何重复利用,和背包问题有点像,留待第二遍再解决
class Solution {
public:
int minDistance(string word1, string word2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int ** dp = new int*[word1.size() + 1];
for(int i = 0; i < word1.size() + 1; i++){
dp[i] = new int[word2.size() + 1];
}
for(int i = 0; i < word1.size() + 1; i++){
dp[i][0] = i;
}
for(int j = 0; j < word2.size() + 1; j++){
dp[0][j] = j;
}
for(int i = 1; i < word1.size() + 1; i++){
for(int j = 1; j < word2.size() + 1; j++){
if (word1[i-1] == word2[j-1]){
//相等的情况下,最后一个元素不占用操作
dp[i][j] = dp[i-1][j-1];
}else{
//delete一种串
dp[i][j] = min(dp[i-1][j] + 1,dp[i][j-1] + 1);
//i和j的位置进行replace
dp[i][j] = min(dp[i][j],dp[i-1][j-1] + 1);
}
}
}
int ans = dp[word1.size()][word2.size()];
for(int i = 0; i < word1.size() + 1; i++){
delete []dp[i];
}
delete []dp;
return ans;
}
};
原文链接: https://www.cnblogs.com/kwill/p/3182882.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/95295
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!