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
class Solution { public: int min3(int a, int b, int c) { return min(min(a,b), c); } int get_dp(int i, int j) { if (i == 0 || j == 0) return max(i, j); return dp[i%2][j]; } int dp[2][100000]; int minDistance(string word1, string word2) { memset(dp, 0, sizeof(dp)); int l1 = word1.size(), l2 = word2.size(); for (int i = 1; i <= l1; i++) { for (int j = 1; j <= l2; j++) { if (word1[i-1] == word2[j-1]) dp[i%2][j] = get_dp(i-1,j-1); else { dp[i%2][j] = min3(get_dp(i-1,j-1), get_dp(i-1,j), get_dp(i,j-1)) + 1; } } } return get_dp(l1,l2); } };
相关推荐
idea leetcode插件 安装方法选择install plugn from disk
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
leetcode中文版
vs code LeetCode 插件
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
leetcode编辑器leetcode-问题 自定义代码演示 leetcode 编辑器配置 代码文件名: $ ! velocityTool . camelCaseName(${question . titleSlug}) 代码模板: ${question . content} package ...
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
leetcode高频面试笔试题150+道,亲身总结。
LeetCode面试笔试题
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
LeetCode 刷题笔记
LeetCode 刷题
(C++)LeetCode刷题题解答案