给定一个字符串和一个字符串字典,找到字典里面最长的字符串,该字符串可以通过删除给定字符串的某些字符来得到。 如果答案不止一个,返回长度最长且字典顺序最小的字符串。如果答案不存在,则返回空字符串。
示例 1:
输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
输出:
"apple"
示例 2:
输入:
s = "abpcplea", d = ["a","b","c"]
输出:
"a"
说明:
所有输入的字符串只包含小写字母。
字典的大小不会超过 1000。
所有输入的字符串长度不会超过 1000。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution { //C++
public:
string findLongestWord(string s, vector<string>& d) {
string ans;
int i, j, k;
for(i = 0; i < d.size(); ++i)
{
for(j = k = 0; j <s.size() && k<d[i].size(); ++j)
{
if(s[j] == d[i][k])//匹配了,移动一位
k++;
}
if(k == d[i].size())//都匹配过了
{
if(d[i].size() > ans.size())
ans = d[i];
else if(d[i].size() == ans.size() && d[i] < ans)
ans = d[i];
}
}
return ans;
}
};
148 ms 14.8 MB
class Solution:# py3
def findLongestWord(self, s: str, d: List[str]) -> str:
ans = ""
n = len(d)
m = len(s)
for i in range(n):
j = k = 0
while j < m and k < len(d[i]):
if s[j]==d[i][k]:
k += 1
j += 1
if k==len(d[i]):
if (len(d[i]) > len(ans)) or (len(d[i])==len(ans) and d[i] < ans):
ans = d[i]
return ans
724 ms 16 MB