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.
暂时没有想到较好的想法,只是最粗鲁的:比较每个字符串与原串,并记录具有最大长度,或者最大程度里面字母序最小的字符串。
string compare_str(string &str1, string str2){
if (str2.size() > str1.size())return str2;
else if (str2.size() < str1.size())return str1;
else return str1 < str2 ? str1 : str2;
}
string findLongestWord(string s, vector<string>& d) {
if (s == "" || d.size() == 0)return "";
string ss = "";
for (auto str : d){
if (str.size() > s.size())continue;
int size = str.size();
int k = 0, i = 0;
while (i < s.size() && k < size){
if (s[i] == str[k])i++, k++;
else i++;
}
if (k == size)ss = compare_str(ss, str);
}
return ss;
}