LeetCode Longest Word in Dictionary through Deleting Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string. Example 1:

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output:
"apple"

Example 2:

Input:
s = "abpcplea", d = ["a","b","c"]
Output:
"a"

Note:

1. All the strings in the input will only contain lower-case letters.
2. The size of the dictionary won’t exceed 1,000.
3. The length of all the strings in the input won’t exceed 1,000.

---

给定一个字典d和字符串s，问d中哪些字符串可以通过s删除若干个字符得到，要求输出满足条件的最长字符串，如果有多个，则输出字典序最小的。 本题有两个考点，一是判断t是否能通过删除s中的若干个字符得到。使用两个指向s,t的指针i,j，j不断后移找t[i]，找到之后i,j都后移。最终如果找到t中所有字符，则成功，否则失败。 另一个考点是，找出所有满足条件的字符串之后，怎样找到长度最长且字典序最小的字符串。这可以通过自定义string的比较函数，然后sort得到。具体看代码： [cpp] bool comp(const string& s1, const string& s2) { return s1.size() > s2.size() || (s1.size() == s2.size() && s1 < s2); } class Solution { private: bool convert(const string& src, const string& dest){ int m = src.size(), n = dest.size(); if (m < n)return false; int i = 0, j = 0; while (i < m) { while (i < m && src[i] != dest[j])++i; if (i >= m)break; ++i; ++j; if (j == n)break; } return j == n; } public: string findLongestWord(string s, vector<string>& d) { vector<string> cand; for (int i = 0; i < d.size(); ++i) { if (convert(s, d[i]))cand.push_back(d[i]); } sort(cand.begin(), cand.end(), comp); if (cand.size() > 0)return cand[0]; else return ""; } }; [/cpp] 本代码提交AC，用时135MS。]]>