524. 通过删除字母匹配到字典里最长单词
双指针
对列表里的每一个字母进行匹配测试，如果可以完全匹配，再与已有结果进行对比，找到最优解。
class Solution { public: string findLongestWord(string s, vector<string> &dictionary) { string res = ""; for (auto &&word : dictionary) { int i = 0, j = 0; while (i < word.length() && j < s.length()) { if (word[i] == s[j]) { i++; } j++; } if (i == word.length()) { if (i > res.length() || (i == res.length() && word < res)) { res = word; } } } return res; } };
排序
先将 dictionary 依据字符串长度的降序和字典序的升序进行排序，然后从前向后找到第一个符合条件的字符串直接返回即可。
class Solution { public: static bool compare(const string &a, const string &b) { if (a.length() == b.length()) { return a < b; } else { return a.length() > b.length(); } } string findLongestWord(string s, vector<string> &dictionary) { sort(dictionary.begin(), dictionary.end(), compare); for (auto &&i : dictionary) { cout << i << endl; } string res = ""; for (auto &&word : dictionary) { int i = 0, j = 0; while (i < word.length() && j < s.length()) { if (word[i] == s[j]) { i++; } j++; } if (i == word.length()) { res = word; break; } } return res; } };
