题目链接
https://leetcode.cn/problems/edit-distance/description/
题目大意
题目代码【记忆化搜索】
class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.size(),m = word2.size();
vector<vector<int>>memo(n,vector<int>(m,-1));
function<int(int,int)>dfs = [&](int i,int j)->int{
if(i < 0) return j + 1;
if(j < 0) return i + 1;
if(memo[i][j] != -1) return memo[i][j];
if(word1[i] == word2[j]) return memo[i][j] = dfs(i - 1,j - 1);
else{
// 替换字符 删除字符 插入字符
return memo[i][j] = min({dfs(i - 1,j - 1),dfs(i - 1,j),dfs(i,j - 1)}) + 1;
}
};
return dfs(n - 1,m - 1);
}
};
标签:return,int,memo,dfs,编辑,word1,距离,word2
From: https://www.cnblogs.com/gebeng/p/18119202