目录
题目：494. 目标和
难度： 中等
题目：
给你一个字符串 s 和一个字符串数组 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] 仅由小写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
题意，字符串数组 dictionary 在字符串s中匹配从前往后匹配字符，能完全匹配的最长且字典序最小的字符串即为所求。
坑点，注意不能单纯使用哈希表匹配，因为字符串匹配是有顺序的，其实本质上是求子序列的问题。
（1）双指针
双指针很好理解，一个指针i表示s的位置，一个指针j表示str的位置，j在遍历时一直往后移动，如果s[i] == str[j]，i才往后移动。匹配时若i到了尽头，则表示匹配成功。
class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
//处理
string ans;
int n = s.size();
for (auto& str : dictionary)
{
int m = str.size();
int i = 0, j = 0;
while (i < m && j < n)
{
if (str[i] == s[j]) i++;
j++;
}
//处理
if (i == m)
{
if (str.size() > ans.size())
{
ans = str;
}
else if (str.size() == ans.size() && str < ans)
{
ans = str;
}
}
}
return ans;
}
};
（2）排序+双指针
题意，需要我们找到长度最大且字典序最小的字符串，那么我们可以在之前先将字符串数组 dictionary 按长度、字典序排序，那么双指针匹配的第一个元素即为所求。
实际上思路和双指针一直。
class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
//处理
string ans;
int n = s.size();
sort(dictionary.begin(), dictionary.end(), [&](string& op1, string& op2) {
return op1.size() != op2.size() ? op1.size() > op2.size() : op1 < op2;
});
for (auto& str : dictionary)
{
int m = str.size();
int i = 0, j = 0;
while (i < m && j < n)
{
if (str[i] == s[j]) i++;
j++;
}
//处理
if (i == m)
{
ans = str;
break;
}
}
return ans;
}
};