# 524.通过删除字母匹配到字典里最长单词

## 问题描述
[524. 通过删除字母匹配到字典里最长单词 (Medium)](https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting/)

给你一个字符串 `s` 和一个字符串数组 `dictionary` ，找出并返回 `dictionary`
中最长的字符串，该字符串可以通过删除 `s` 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

**示例 1：**

```
输入：s = "abpcplea", dictionary =
["ale","apple","monkey","plea"]
输出："apple"

```

**示例 2：**

```
输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"

```

**提示：**

- `1 <= s.length <= 1000`
- `1 <= dictionary.length <= 1000`
- `1 <= dictionary[i].length <= 1000`
- `s` 和 `dictionary[i]` 仅由小写英文字母组成

## 解题思路
首先将`dictionary`按长度从大到小排序，相同长度的字符串，字典序小的在前面；

判断`dictionary`中的字符串是否能通过删除`s`中的某些字符得到可以利用双指针优化时间复杂度为$O(n)$，`n`为`s`的长度。

## 代码
```cpp
class Solution {
  public:
    bool IsSub(string &s, string &word) {
        for (int i = 0, j = 0; j < word.size();) {
            if (i == s.size()) {
                return false;
            }
            if (s[i] == word[j]) {
                i++;
                j++;
            } else {
                i++;
            }
        }
        return true;
    }
    string findLongestWord(string s, vector<string> &dictionary) {
        auto cmp = [&](string &s1, string &s2) {
            if (s1.size() != s2.size()) {
                return s1.size() > s2.size();
            }
            return s1 < s2;
        };
        std::sort(dictionary.begin(), dictionary.end(), cmp);
        for (auto &word : dictionary) {
            if (IsSub(s, word)) {
                return word;
            }
        }
        string res;
        return res;
    }
};
```