2019-07-22.md

毎日一题 - 524.longest-word-in-dictionary-through-deleting

信息卡片

• 时间：2019-07-22
• 题目链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/
• tag：String Two Pointers

题目描述

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

示例 1:

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

输出:
"apple"
示例 2:

输入:
s = "abpcplea", d = ["a","b","c"]

输出:
"a"
说明:

1. 所有输入的字符串只包含小写字母。
2. 字典的大小不会超过 1000。
3. 所有输入的字符串长度不会超过 1000。

参考答案

我们的思路是删除字符串中的某些字符，使得可以组成数组中的字符串， 然后我们找到最长。

字符串删除某些字符，使之成为另一个字符串，这本质上是字符串子序列问题。

求解 subSequence 的题目，可以用双指针解决 比如在字符串 a 中查找 b，那么快指针在 a 上，慢指针在 b。 快指针一直更新，慢指针只有两个相等才更新 最后比较慢指针是否走到底了即可

参考JavaScript代码：

function isSequence(s, word) {
  if (word.length > s.length) return false;

  let i = 0;
  let j = 0;

  while(i < s.length && j < s.length) {
    if (word[i] === s[j]) i++;
    j++;
  }

  // 说明有s中有word.length个元素和word匹配（且顺序一致）
  // 换句话说就是word是s的子序列
  return i === word.length;
}
/**
 * @param {string} s
 * @param {string[]} d
 * @return {string}
 */
var findLongestWord = function(s, d) {
  let res = "";

  for (let word of d) {
    if (isSequence(s, word)) {
      if (word.length > res.length) res = word;
      else if (word.length === res.length && word.charAt(0) < res.charAt(0))
        res = word;
    }
  }

  return res;
};

优秀解答

暂缺