新疆网站建设咨询北京seo工程师
前言
题目:72. 编辑距离
参考题解:编辑距离-代码随想录、编辑距离-力扣官方题解
提交代码
用未知的方法,去解决不确定的问题,心累了。不想干事,想刷个题找找短期反馈,结果还卡住了。
晚上去后湖溜溜步。洗个澡,今晚还是得把这道题目给通过。
这道题目确实有点难。看了答案才明白。思路见参考题解中的链接。下面代码入为理解之后,自行写一遍。
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));// 初始化。从当前串变成空串for(int i=0; i<=word1.size(); i++){dp[i][0] = i;}for(int i=0; i<=word2.size(); i++){dp[0][i] = i;}for(int i=1; i<=word1.size(); i++){for(int j=1; j<=word2.size(); j++){if(word1[i-1] == word2[j-1])dp[i][j] = dp[i-1][j-1]; // 不需要做修改elsedp[i][j] = min(dp[i-1][j-1]+1, min(dp[i-1][j]+1, dp[i][j-1]+1)); // 分别为修改最后一个字符;对与A的第i个字符,B在后面添加一个字符;对于B的第j个字符,在A的后面添加一个字符}}return dp[word1.size()][word2.size()];}
};