leecode/daily/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代码：


```js

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

```

## 优秀解答

> 暂缺