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