链接
https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/
耗时
解题：12 min
题解：17 min
题意
给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。
提示：
1 <= s.length <= 10001 <= dictionary.length <= 10001 <= dictionary[i].length <= 1000s 和 dictionary[i] 仅由小写英文字母组成
思路
暴力。遍历字典中的所有单词，看这个单词是否是 s 的子序列（遍历一遍 s，按 word 的字符顺序看 word 每个字符是否在 s 中即可），如果是子序列，看当前 word 是不是比结果是长度更长或者长度相等但字典序更小。
时间复杂度：
O
(
d
i
c
t
i
o
n
a
r
y
.
l
e
n
g
t
h
∗
s
.
l
e
n
g
t
h
)
O(dictionary.length*s.length)
O(dictionary.length∗s.length)
AC代码
class Solution {
public String findLongestWord(String s, List<String> dictionary) {
String ans = "";
for(String word : dictionary) {
int pos = 0;
for(int i = 0; i < s.length(); ++i) {
if(word.charAt(pos) == s.charAt(i)) {
pos++;
if(pos == word.length()) {
if(word.length() > ans.length()) {
ans = word;
}
else if((word.length() == ans.length()) && (word.compareTo(ans) < 0)) {
ans = word;
}
break;
}
}
}
}
return ans;
}
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
