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 <= 10001 <= dictionary.length <= 10001 <= dictionary[i].length <= 1000s 和 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 遍历 dic while (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 遍历 dictionary while (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. 筛选符合条件的字符串：

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