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了戴而。