当前位置:网站首页>leetcode 72. Edit Distance 编辑距离(中等)
leetcode 72. Edit Distance 编辑距离(中等)
2022-07-04 21:43:00 【InfoQ】
一、题目大意
- 0 <= word1.length, word2.length <= 500
- word1 和 word2 由小写英文字母组成
二、解题思路
三、解题方法
3.1 Java实现
public class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0) {
dp[i][j] = j;
} else if (j == 0) {
dp[i][j] = i;
} else {
dp[i][j] = Math.min(
dp[i - 1][j - 1] + (word1.charAt(i - 1) == word2.charAt(j - 1) ? 0 : 1),
Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
);
}
}
}
return dp[m][n];
}
}
四、总结小记
- 2022/7/4 坚持每天一题
边栏推荐
- 案例分享|金融业数据运营运维一体化建设
- 从RepVgg到MobileOne,含mobileone的代码
- 机器人相关课程考核材料归档实施细则2022版本
- VS2019 C# release下断点调试
- 能源势动:电力行业的碳中和该如何实现?
- MySQL存储数据加密
- VIM from dislike to dependence (23) -- the last gossip
- ACM multimedia 2022 | counterfactual measurement and elimination of social prejudice in visual language pre training model
- 赋能数字经济 福昕软件出席金砖国家可持续发展高层论坛
- gtest从一无所知到熟练使用(4)如何用gtest写单元测试
猜你喜欢
Scala下载和配置
[optimtool.unconstrained] unconstrained optimization toolbox
常用的开源无代码测试工具
How to remove the black dot in front of the title in word document
QT - plot other problems
El tree combined with El table, tree adding and modifying operations
Enabling digital economy Fuxin software attends the BRICs high level Forum on Sustainable Development
Huawei Nova 10 series released Huawei application market to build a solid application security firewall
Interpreting the development of various intelligent organizations in maker Education
机器学习笔记 - 互信息Mutual Information
随机推荐
Cloudcompare & open3d DBSCAN clustering (non plug-in)
CloudCompare&Open3D DBSCAN聚类(非插件式)
AscendEX 上线 Walken (WLKN) - 一款卓越领先的“Walk-to-Earn”游戏
Nat. Commun.| 机器学习对可突变的治疗性抗体的亲和力和特异性进行共同优化
gtest从一无所知到熟练使用(3)什么是test suite和test case
传智教育|如何转行互联网高薪岗位之一的软件测试?(附软件测试学习路线图)
WebGIS framework -- kalrry
283. Moving zero-c and language assisted array method
Representation of confidence interval
Flink1.13 SQL basic syntax (I) DDL, DML
Play with grpc - go deep into concepts and principles
A large number of virtual anchors in station B were collectively forced to refund: revenue evaporated, but they still owe station B; Jobs was posthumously awarded the U.S. presidential medal of freedo
File read write
迷失在Mysql的锁世界
关系型数据库
WebGIS框架---kalrry
[early knowledge of activities] list of recent activities of livevideostack
Hash table
面试题 01.08. 零矩阵
HDU - 2859 Phalanx(DP)