524. Longest Word in Dictionary through Deleting

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

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末凑术,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子所意,更是在濱河造成了極大的恐慌淮逊,老刑警劉巖,帶你破解...
    沈念sama閱讀 223,002評(píng)論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件扁眯,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡翅帜,警方通過(guò)查閱死者的電腦和手機(jī)姻檀,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)涝滴,“玉大人绣版,你說(shuō)我怎么就攤上這事胶台。” “怎么了杂抽?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,787評(píng)論 0 365
  • 文/不壞的土叔 我叫張陵诈唬,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我缩麸,道長(zhǎng)铸磅,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,237評(píng)論 1 300
  • 正文 為了忘掉前任杭朱,我火速辦了婚禮阅仔,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘弧械。我一直安慰自己八酒,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布刃唐。 她就那樣靜靜地躺著羞迷,像睡著了一般。 火紅的嫁衣襯著肌膚如雪画饥。 梳的紋絲不亂的頭發(fā)上衔瓮,一...
    開(kāi)封第一講書(shū)人閱讀 52,821評(píng)論 1 314
  • 那天,我揣著相機(jī)與錄音荒澡,去河邊找鬼报辱。 笑死,一個(gè)胖子當(dāng)著我的面吹牛单山,可吹牛的內(nèi)容都是我干的碍现。 我是一名探鬼主播,決...
    沈念sama閱讀 41,236評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼米奸,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼昼接!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起悴晰,我...
    開(kāi)封第一講書(shū)人閱讀 40,196評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤慢睡,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后铡溪,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體漂辐,經(jīng)...
    沈念sama閱讀 46,716評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評(píng)論 3 343
  • 正文 我和宋清朗相戀三年棕硫,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了髓涯。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,928評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡哈扮,死狀恐怖纬纪,靈堂內(nèi)的尸體忽然破棺而出蚓再,到底是詐尸還是另有隱情,我是刑警寧澤包各,帶...
    沈念sama閱讀 36,583評(píng)論 5 351
  • 正文 年R本政府宣布摘仅,位于F島的核電站,受9級(jí)特大地震影響问畅,放射性物質(zhì)發(fā)生泄漏娃属。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評(píng)論 3 336
  • 文/蒙蒙 一按声、第九天 我趴在偏房一處隱蔽的房頂上張望膳犹。 院中可真熱鬧,春花似錦签则、人聲如沸须床。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,755評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)豺旬。三九已至,卻和暖如春柒凉,著一層夾襖步出監(jiān)牢的瞬間族阅,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,869評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工膝捞, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留坦刀,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,378評(píng)論 3 379
  • 正文 我出身青樓蔬咬,卻偏偏與公主長(zhǎng)得像鲤遥,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子林艘,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容