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.?篩選符合條件的字符串：

因為前面已經將字典進行排序，而且字典優先按長度降序排列，如果長度相同則按字典序升序排列。也就是說，第一個找到的字符串就是最符合要求的答案