Medium
隨便寫了個(gè)自認(rèn)為很暴力的方法荆虱,居然AC了而且速度排在中游吧先誉,吃驚拌阴,真的是幾百年沒(méi)有不看答案寫出來(lái)了绍绘,/(ㄒoㄒ)/~~
我一向是推崇邏輯最簡(jiǎn)單的方法,越straightforward越好迟赃,越general越好陪拘,總之就是越好理解使用場(chǎng)景越頻繁越能通用就越好。我最怕那種特別fancy花哨感的方法纤壁,看過(guò)之后最多能當(dāng)天重寫一遍左刽,以后完全不會(huì)自己用。
首先酌媒,確定given string的所有字符欠痴,如果dict里某個(gè)單詞里有string沒(méi)有的字符迄靠,那么它肯定不能由該string刪除掉字母變得。這個(gè)時(shí)候用hashSet裝字母斋否,再以此遍歷dict的每個(gè)單詞查就可以梨水。
光是有該單詞的所有字母還不能保證就一定能由given string刪除字符得到,比如字母順序不一樣茵臭, alpepa就不能刪成apple. 所以我們用two pointers同時(shí)遍歷given string和dict word的所有字符疫诽,從index == 0開(kāi)始,如果字符相同旦委,則同時(shí)右移奇徒;如果字符不同,我們就通過(guò)右移given string的指針來(lái)“刪”缨硝, 繼續(xù)比較摩钙。如果退出while循環(huán)的時(shí)候,dict word的pointer的index是word.length()時(shí)查辩,說(shuō)明我們已經(jīng)在given string里找到了一個(gè)完整的dict word, 也就是說(shuō)明我們確實(shí)可以由given word刪字母變?yōu)閐ict word.
找到所有可能由given word變成的dict word之后胖笛,我們?cè)僬页鲎铋L(zhǎng)的,并且lexicographical order靠最前的宜岛。用Collections.sort就可以實(shí)現(xiàn)字母排序长踊,再遍歷找maxLen的就可以。
class Solution {
public String findLongestWord(String s, List<String> d) {
Set<String> dict = new HashSet<>(d);
Set<Character> chars = new HashSet<>();
for (char c : s.toCharArray()){
chars.add(c);
}
List<String> possibleWords = new ArrayList<>();
for (String str : dict){
if (str.length() > s.length()){
continue;
}
for (Character c : str.toCharArray()){
if (!chars.contains(c)){
continue;
}
}
int i = 0, j = 0;
while (i < s.length() && j < str.length()){
if (s.charAt(i) != str.charAt(j)){
i++;
} else {
i++;
j++;
}
}
if (j == str.length()){
possibleWords.add(str);
}
}
int maxLen = 0;
String res = "";
Collections.sort(possibleWords);
for (String st : possibleWords){
if (st.length() > maxLen){
maxLen = st.length();
res = st;
}
}
return res;
}
}
我的code整理一下簡(jiǎn)化一下應(yīng)該就長(zhǎng)下面這樣萍倡,可以先sort.學(xué)到了String.compareTo(another string)直接就是Compares two strings lexicographically.
class Solution {
public String findLongestWord(String s, List<String> dict) {
Collections.sort(dict, new Comparator<String>(){
public int compare(String a, String b){
if (a.length() == b.length()){
return a.compareTo(b);
} else {
return b.length() - a.length();
}
}
});
int maxLen = 0;
String res = "";
for (String word : dict){
int i = 0, j = 0;
while (i < s.length() && j < word.length()){
if (s.charAt(i) == word.charAt(j)){
i++;
j++;
} else {
i++;
}
}
if (j == word.length()){
if (word.length() > maxLen){
maxLen = word.length();
res = word;
}
}
}
return res;
}
}
注意一下 我們所說(shuō)的linear time的complexity是針對(duì)于input而言的身弊。所以這里的input就是一個(gè)np的,你是字典size列敲,p是給的字符串的長(zhǎng)度阱佛,所以我們的方法雖然也是np,但它相對(duì)于input就是linear time了戴而。