这道题对我来说开始没有思路,主要是没有抽象出来删除字符变为target应该如何简单实现?
看了一眼讨论区代码,知道如何实现后,又卡在了判断条件处,先根据长度简单判断,最后更新结果时判断能否通过删除字符得到target.
class Solution {
public:
string findLongestWord(string s, vector<string>& d) {
string res;
for(int i = 0;i < d.size();i++)
{
if(d[i].size() >res.size() ||
(d[i].size() == res.size() && d[i].compare(res) < 0)
)
{
if(isSubstr(s,d[i]))
res = d[i];
}
}
return res;
}
private:
//判断s能否通过删除字符得到target
bool isSubstr(string s, string target) {
int i = 0,j = 0;
int size = target.size();
while(i < s.size() && j < target.size())
{
if(s[i] == target[j])
j++;
i++;
}
return j == target.size();
}
};
运行结果:
Runtime: 68 ms, faster than 69.34% of C++ online submissions for Longest Word in Dictionary through Deleting.
Memory Usage: 22.5 MB, less than 32.81% of C++ online submissions for Longest Word in Dictionary through Deleting.