两个字符串的删除操作

两个字符串的删除操作

Posted by LY on March 19, 2019

在这里小小推荐下我的个人博客

csdn:雷园的csdn博客

个人博客:雷园的个人博客

简书:雷园的简书

前言

  1. 今天我们继续来说一道算法题目!!!
  2. 看到关注我的同学们大多都年纪不大,应该大多都是在上学的小伙伴。
  3. 其实吧!!!我的年纪也不大,希望我们可以有共同语言,大家在学习上有什么不懂得、学不会的、感觉学起来很吃力的同学可以来找我,我们可以一起探讨学习的方式!!!
  4. 共同努力,共同进步嘛。

题目:

给定两个单词 word1word2,找到使得 word1和word2相同所需的最小步数,每步可以删除任意一个字符串中的一个字符。

示例 1:

输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea",第二步将"eat"变为"ea"

说明:

  1. 给定单词的长度不超过500。
  2. 给定单词中的字符只含有小写字母。

解题思路

  1. 今天这道题目看起来并不是很难,因为题目比较简短。
  2. 我们先来分析一下题目要求。
  3. 首先,他说我们要使 word1和word2相同。依照这句话,我们可以把这个问题转移到寻找字符串的公共子序列。
  4. 其次,他说 我们需要使用最短的步数找到结果。那依照这句话,我们可以把问题继续细化到寻找字符串的最长公共子序列
  5. 最后还需要注意的是,他要求我们 每一步可以删除任意一个字符串中的一个字符,也就是说我们每一步只能操作一个字符串中的一个字符

代码实现

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];
}

最后说两句

  1. 所有的题目都有很多种解法,我的一定不是最好的,甚至可以说是比较低端的解法,希望大牛们多多指教!!!
  2. 如果朋友们对算法、编程有很大兴趣的话,可以私信我,大家一同探讨;相互学习、共同进步。
  3. 朋友们如果对这道题目有更好的解法,希望可以在评论中指出,让大家一起讨论学习。
  4. 最后感谢大家的阅读以及关注,谢谢大家!!!

最后的最后

给大家推荐一本书⬇️。