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

1、题目描述：

给你一个字符串 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] 仅由小写英文字母组成

---

2、代码：

高逼格代码：

class Solution {
public:string findLongestWord(string s, vector<string>& dictionary) {// 定义一个 lambda 表达式 compareStr，用于判断字典中的字符串是否是 s 的子序列auto compareStr = [&](const string& s, const string& dic) -> bool {int i = 0, j = 0; // i 遍历 s，j 遍历 dicwhile (i < s.size() && j < dic.size()) { // 双指针遍历两个字符串if (s[i] == dic[j]) { // 如果字符匹配，移动 dic 的指针++j;}++i; // 始终移动 s 的指针}return j == dic.size(); // 如果 dic 被完全匹配，返回 true};// 对字典进行排序：优先按长度降序排列，如果长度相同则按字典序升序排列sort(dictionary.begin(), dictionary.end(),[](const string& a, const string& b) {return (a.size() == b.size()) ? (a < b) : (a.size() > b.size());});// 遍历排序后的字典，找到第一个符合条件的字符串for (auto str : dictionary) {if (compareStr(s, str)) { // 如果当前字符串是 s 的子序列return str; // 返回该字符串}}// 如果没有找到符合条件的字符串，返回空字符串return "";}
};

普通代码 ：

class Solution {
public:// 判断字典中的字符串 dictionary 是否是字符串 s 的子序列bool compareStr(const string& s, const string& dictionary) {int i = 0, j = 0; // i 遍历 s，j 遍历 dictionarywhile (i < s.size() && j < dictionary.size()) { // 双指针遍历两个字符串if (s[i] == dictionary[j]) { // 如果字符匹配，移动 dictionary 的指针++j;}++i; // 始终移动 s 的指针}return j == dictionary.size(); // 如果 dictionary 被完全匹配，返回 true}// 主函数：从字典中找到最长且符合条件的字符串string findLongestWord(string s, vector<string>& dictionary) {// 如果字符串 s 为空，直接返回空字符串（题目保证 s 不为空，此检查可省略）if (s == "") {return "";}// 对字典进行排序：优先按长度降序排列，如果长度相同则按字典序升序排列sort(dictionary.begin(), dictionary.end(),[](const string& a, const string& b) {if (a.size() != b.size()) // 如果长度不同，按长度降序排列return a.size() > b.size();return a < b; // 如果长度相同，按字典序升序排列});// 遍历排序后的字典，找到第一个符合条件的字符串for (auto str : dictionary) {if (compareStr(s, str)) { // 如果当前字符串是 s 的子序列return str; // 返回该字符串}}// 如果没有找到符合条件的字符串，返回空字符串return "";}
};

---

3、解题思路：

1.判断子序列 ：

这是一个双指针的问题，双指针应用在哪呢？就是用在辅助函数里，来判断某个字符串是否是另一个字符串的子序列，具体方法是使用双指针，分别遍历 s 和目标字符串 dictionary，检查 dictionary是否可以通过删除 s 的某些字符得到。

2. 优化排序 ：

为了方便比较长度和字典序，可以先对字典进行排序：优先按长度降序排列，如果长度相同则按字典序升序排列。

3. 筛选符合条件的字符串：

因为前面已经将字典进行排序，而且字典优先按长度降序排列，如果长度相同则按字典序升序排列。也就是说，第一个找到的字符串就是最符合要求的答案