欢迎大家关注我的以下主页，尤其是今日头条！！！谢谢🙏🙏🙏
csdn：雷园的csdn博客
个人博客：雷园的个人博客
简书：雷园的简书
今日头条：来自底层程序员的仰望
前言
- 今天我们继续来说一道算法题目!!!
- 看到关注我的同学们大多都年纪不大，应该大多都是在上学的小伙伴。
- 其实吧!!!我的年纪也不大，希望我们可以有共同语言，大家在学习上有什么不懂得、学不会的、感觉学起来很吃力的同学可以来找我，我们可以一起探讨学习的方式!!!
- 共同努力，共同进步嘛。
题目：
给定两个单词 word1 和 word2，找到使得 word1和word2相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
示例 1:
输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
说明:
- 给定单词的长度不超过500。
- 给定单词中的字符只含有小写字母。
解题思路
- 今天这道题目看起来并不是很难，因为题目比较简短。
- 我们先来分析一下题目要求。
- 首先，他说我们要使 word1和word2相同。依照这句话，我们可以把这个问题转移到寻找字符串的公共子序列。
- 其次，他说 我们需要使用最短的步数找到结果。那依照这句话，我们可以把问题继续细化到寻找字符串的最长公共子序列。
- 最后还需要注意的是，他要求我们 每一步可以删除任意一个字符串中的一个字符，也就是说我们每一步只能操作一个字符串中的一个字符。
代码实现
public int minDistance(String word1, String word2) {
// 定义两个单词的长度
int len1 = word1.length();
int len2 = word2.length();
// 定义answer[i][j]表示word1与word2的最大公共子序列长度
int[][] answer = new int[len1 + 1][len2 + 1];
// 动态规划求解最长公共子序列长度
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
// 判断字符是否相同
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
answer[i][j] = answer[i - 1][j - 1] + 1;
} else {
answer[i][j] = Math.max(answer[i - 1][j], answer[i][j - 1]);
}
}
}
// 返回结果为两单词长度和减去两倍的最长公共子序列长度
return len1 + len2 - 2 * answer[len1][len2];
}
最后说两句
- 所有的题目都有很多种解法，我的一定不是最好的，甚至可以说是比较低端的解法，希望大牛们多多指教！！！
- 如果朋友们对算法、编程有很大兴趣的话，可以私信我，大家一同探讨；相互学习、共同进步。
- 朋友们如果对这道题目有更好的解法，希望可以在评论中指出，让大家一起讨论学习。
- 最后感谢大家的阅读以及关注，谢谢大家！！！
