亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Word Ladder

系統(tǒng) 1883 0

Given two words ( start ?and? end ), and a dictionary, find all transformation sequence(s) from? start ?to? end , such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

?

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

嘗試用Trie 來實現(xiàn)這個。

最后TLE(out of time),不過算法已經(jīng)正確了。?

使用Trie,擴展性更好。 可以時時的加減dict里面的word, 也可以被多次調(diào)用。

      
          1
      
      
        package
      
      
         leetcode;


      
      
          2
      
      
          3
      
      
        import
      
      
         java.util.ArrayList;


      
      
          4
      
      
        import
      
      
         java.util.HashSet;


      
      
          5
      
      
        import
      
      
         java.util.Iterator;


      
      
          6
      
      
        import
      
      
         java.util.List;


      
      
          7
      
      
        import
      
      
         java.util.Set;


      
      
          8
      
      
          9
      
      
        //
      
      
        implement wordLadder with Trie.
      
      
         10
      
      
        /*
      
      
         11
      
      
         * 如果這個函數(shù)要多次被調(diào)用,怎么辦?


      
      
         12
      
      
         * 因為我每次都用挨個修改字母的辦法來尋找新word,但如果能先對dictionary做個預(yù)處理,弄個從word到set of words之間的mapping,那么每輪BFS就可以省去尋找新詞的時間。預(yù)處理字典的復(fù)雜度也是O(size of dictionary) * (length of string) * 26。最終可以用一個Hash<String, Set<String>>來表示這個mapping關(guān)系。


      
      
         13
      
      
         * 


      
      
         14
      
      
         * 如果這個字典要增加/移除單詞怎么辦?


      
      
         15
      
      
         * 增加的話,只需要對新單詞做同樣的事情:修改每個字母找下一個單詞,然后那個被找到下一個單詞的mapping里同時也添加進新單詞。因為這個關(guān)系是可互換的,如果wordA => wordB, 那么wordB => wordA。


      
      
         16
      
      
         * 刪除的時候同理,對于map.get(toBeRemoved)里的所有單詞的mapping集合都刪掉這個toBeRemoved,然后再從map里面去掉它自己,寫出來的代碼大概是這樣:


      
      
         17
      
      
         * for (String s : map.get(toBeRemoved)) map.get(s).remove(toBeRemoved);


      
      
         18
      
      
         * map.remove(toBeRemoved);


      
      
         19
      
      
         * 這個地方我一開始沒注意到可以互換,以為還得預(yù)處理一個反方向的mapping,經(jīng)過面試官兩次提醒才發(fā)現(xiàn)了這個規(guī)律……


      
      
         20
      
      
         * 


      
      
         21
      
      
         * 如果這個字典變得很龐大,這個mapping和字典本身就太占空間了,怎么處理?


      
      
         22
      
      
         * 用trie記錄所有單詞,每個node用一個bit記錄這個node是否為一個單詞,并且有一個set<myTrieNode>的field記錄他可以變成的其他單詞。至于如何構(gòu)建這個field,利用trie的特性,可以用回溯的方法非常簡單地找到可變過去的單詞(在碰到公共ancestor之前,路徑上的node個數(shù)必須相同,這個用于保證長度,并且至多只有一個字母不同,用于滿足mapping的條件)


      
      
         23
      
      
         * 至此……時間終于用完了,問了下他的team的情況,就結(jié)束了……


      
      
         24
      
      
         * 


      
      
         25
      
      
         * 
      
      
        */
      
      
         26
      
      
         27
      
      
        class
      
      
         myTrieNode{


      
      
         28
      
      
            Boolean isWord;


      
      
         29
      
      
            myTrieNode[] childList;


      
      
         30
      
      
            Integer freq;


      
      
         31
      
      
        char
      
      
         val;


      
      
         32
      
      
            String word;


      
      
         33
      
      
         34
      
      
        public
      
       myTrieNode(){
      
        //
      
      
        use to generate root of Trie
      
      
         35
      
      
        this
      
      .freq = 0
      
        ;


      
      
         36
      
      
        this
      
      .childList = 
      
        new
      
       myTrieNode[26
      
        ];


      
      
         37
      
      
        this
      
      .isWord = 
      
        false
      
      
        ;


      
      
         38
      
      
            }


      
      
         39
      
      
         40
      
      
        public
      
       myTrieNode(
      
        char
      
      
         c){


      
      
         41
      
      
        this
      
      .val =
      
         c;


      
      
         42
      
      
        this
      
      .freq = 1
      
        ;


      
      
         43
      
      
        this
      
      .childList = 
      
        new
      
       myTrieNode[26
      
        ];


      
      
         44
      
      
            }


      
      
         45
      
      
         46
      
      
        public
      
      
         String containsWord(String s){


      
      
         47
      
      
        if
      
      (s == 
      
        null
      
       || s.length() == 0
      
        ){


      
      
         48
      
      
        if
      
      (
      
        this
      
      .word != 
      
        null
      
       && 
      
        this
      
      .isWord == 
      
        true
      
      ) 
      
        return
      
      
        this
      
      
        .word;


      
      
         49
      
      
        else
      
      
        return
      
       ""
      
        ;


      
      
         50
      
      
                }


      
      
         51
      
      
        int
      
       len =
      
         s.length();


      
      
         52
      
               myTrieNode cur = 
      
        this
      
      
        ;


      
      
         53
      
      
        for
      
      (
      
        int
      
       i = 0; i < len; i ++
      
        ){


      
      
         54
      
      
        char
      
       c =
      
         s.charAt(i);


      
      
         55
      
      
        if
      
      (cur.childList[c - 'a'] != 
      
        null
      
      
        ){


      
      
         56
      
                       cur = cur.childList[c - 'a'
      
        ];


      
      
         57
      
                   }
      
        else
      
      
        {


      
      
         58
      
      
        return
      
      
        null
      
      
        ;


      
      
         59
      
      
                    }


      
      
         60
      
      
                }


      
      
         61
      
      
        return
      
       cur.isWord == 
      
        true
      
       ? cur.word : 
      
        null
      
      
        ;


      
      
         62
      
      
            }


      
      
         63
      
      
        }


      
      
         64
      
      
        class
      
      
         myTrie{


      
      
         65
      
      
            myTrieNode root;


      
      
         66
      
      
         67
      
      
        public
      
      
         myTrie(){


      
      
         68
      
      
        this
      
      .root = 
      
        new
      
      
         myTrieNode();


      
      
         69
      
      
            }


      
      
         70
      
      
         71
      
      
        public
      
      
        void
      
      
         insert(String word){


      
      
         72
      
      
        if
      
      (word == 
      
        null
      
       || word.length() == 0) 
      
        return
      
      
        ;


      
      
         73
      
      
        int
      
       len =
      
         word.length();


      
      
         74
      
               myTrieNode cur = 
      
        this
      
      
        .root;


      
      
         75
      
      
        for
      
      (
      
        int
      
       i = 0; i < len; i ++
      
        ){


      
      
         76
      
      
        char
      
       c =
      
         word.charAt(i);


      
      
         77
      
      
        if
      
      (cur.childList[c - 'a'] == 
      
        null
      
      
        ){


      
      
         78
      
                       cur.childList[c - 'a'] = 
      
        new
      
      
         myTrieNode(c);


      
      
         79
      
                   }
      
        else
      
      
        {


      
      
         80
      
                       cur.childList[c - 'a'].freq ++
      
        ;


      
      
         81
      
      
                    }


      
      
         82
      
                   cur = cur.childList[c - 'a'
      
        ];


      
      
         83
      
      
        if
      
      (i == word.length() - 1
      
        ){


      
      
         84
      
                       cur.isWord = 
      
        true
      
      
        ;


      
      
         85
      
                       cur.word =
      
         word;


      
      
         86
      
      
                    } 


      
      
         87
      
      
                }


      
      
         88
      
      
            }


      
      
         89
      
      
         90
      
      
        }


      
      
         91
      
      
        public
      
      
        class
      
      
         WordLadder {


      
      
         92
      
      
         93
      
      
         94
      
      
        private
      
      
        static
      
      
         myTrie trie;


      
      
         95
      
      
        private
      
      
        static
      
       List<List<String>>
      
         result;


      
      
         96
      
      
        public
      
      
        static
      
       List<List<String>> findLadders(String start, String end, Set<String>
      
         dict) {


      
      
         97
      
                   trie =
      
         generateTrie(dict);


      
      
         98
      
      
                    trie.insert(end);


      
      
         99
      
                   result = 
      
        new
      
       ArrayList<List<String>>
      
         ();


      
      
        100
      
                   ArrayList<String> row = 
      
        new
      
       ArrayList<String>
      
        ();


      
      
        101
      
      
                    row.add(start);


      
      
        102
      
                   findLadderSequence(start, end, row, 
      
        new
      
       HashSet<String>
      
        ());


      
      
        103
      
      
        return
      
      
         result;


      
      
        104
      
      
                }


      
      
        105
      
      
        106
      
      
        private
      
      
        static
      
      
        void
      
       findLadderSequence(String start, String end, ArrayList<String> row, HashSet<String>
      
         usedSet){


      
      
        107
      
      
        if
      
      
        (start.equals(end)){


      
      
        108
      
      
                        result.add(row);


      
      
        109
      
      
                    }


      
      
        110
      
                   myTrieNode cur =
      
         trie.root;


      
      
        111
      
                   myTrieNode next =
      
         cur;


      
      
        112
      
      
        for
      
      (
      
        int
      
       i = 0; i < start.length(); i ++
      
        ){


      
      
        113
      
      
        char
      
       c =
      
         start.charAt(i);


      
      
        114
      
      
        for
      
      (
      
        int
      
       j = 0; j < 26; j ++
      
        ){


      
      
        115
      
      
        if
      
      (cur.childList[j] != 
      
        null
      
       && cur.childList[j].val ==
      
         c){


      
      
        116
      
                               next =
      
         cur.childList[j];


      
      
        117
      
      
                            }


      
      
        118
      
      
        if
      
      (cur.childList[j] != 
      
        null
      
       && cur.childList[j].val !=
      
         c){


      
      
        119
      
                               String tmp = cur.childList[j].containsWord(start.substring(i + 1
      
        ));


      
      
        120
      
      
        if
      
      (tmp != 
      
        null
      
       && !
      
        usedSet.contains(tmp)){


      
      
        121
      
      
                                    row.add(tmp);


      
      
        122
      
      
                                    usedSet.add(tmp);


      
      
        123
      
                                   findLadderSequence(tmp, end, 
      
        new
      
       ArrayList<String>(row), 
      
        new
      
       HashSet<String>
      
        (usedSet));


      
      
        124
      
                                   row.remove(row.size() - 1
      
        );


      
      
        125
      
      
                                    usedSet.remove(tmp);


      
      
        126
      
      
                                }


      
      
        127
      
      
                            }


      
      
        128
      
      
                        }


      
      
        129
      
                       cur =
      
         next;


      
      
        130
      
      
                    }


      
      
        131
      
      
        132
      
      
                }


      
      
        133
      
      
        134
      
      
        private
      
      
        static
      
       myTrie generateTrie(Set<String>
      
         dict){


      
      
        135
      
                   myTrie trie = 
      
        new
      
      
         myTrie();


      
      
        136
      
      
        if
      
      (dict.isEmpty()) 
      
        return
      
      
         trie;


      
      
        137
      
      
        //
      
      
        generate Trie for dictionary
      
      
        138
      
                   Iterator it =
      
         dict.iterator();


      
      
        139
      
      
        while
      
      
        (it.hasNext()){


      
      
        140
      
                       String word =
      
         (String)it.next();


      
      
        141
      
      
                        trie.insert(word);


      
      
        142
      
      
                    }


      
      
        143
      
      
        return
      
      
         trie;


      
      
        144
      
      
                }


      
      
        145
      
      
        146
      
      
        public
      
      
        static
      
      
        void
      
      
         main(String[] args){


      
      
        147
      
               String start = "hit"
      
        ;


      
      
        148
      
               String end = "cog"
      
        ;


      
      
        149
      
               Set<String> dict = 
      
        new
      
       HashSet<String>
      
        ();


      
      
        150
      
               dict.add("hot"
      
        );


      
      
        151
      
               dict.add("dot"
      
        );


      
      
        152
      
               dict.add("dog"
      
        );


      
      
        153
      
               dict.add("lot"
      
        );


      
      
        154
      
               dict.add("log"
      
        );


      
      
        155
      
      
                findLadders(start, end, dict);


      
      
        156
      
      
                System.out.println(result);


      
      
        157
      
      
            }


      
      
        158
      
       }
    

?Output:

[[hit, hot, dot, lot, log, cog],

[hit, hot, dot, lot, log, dog, cog],

[hit, hot, dot, dog, cog],

[hit, hot, dot, dog, log, cog],

[hit, hot, lot, dot, dog, cog],

[hit, hot, lot, dot, dog, log, cog],

[hit, hot, lot, log, cog],

[hit, hot, lot, log, dog, cog]]

Word Ladder


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 日本一级毛片a免费播放 | 奇米影视第| 91在线亚洲 | 欧美一区二区在线观看免费网站 | 91不卡在线精品国产 | 久久91精品国产一区二区 | 免费日韩在线视频 | 免费视频爱爱太爽了 | 亚洲图片国产日韩欧美 | 久久精品夜夜夜夜夜久久 | 国产精品自在自线免费观看 | 综合欧美日韩一区二区三区 | 国产精品99精品久久免费 | 国产日韩久久 | 成人www视频网站免费观看 | www.夜夜| 久久久久在线观看 | 操美女的穴| 美女一级免费毛片 | 日本一本二本免费播放视频 | 在线观看免费精品国产 | 中文一区二区 | 国产亚洲欧美一区二区三区 | 2021最新国产成人精品免费 | 狠狠ai| 日韩女同视频 | 精品视频免费 | 97av在线视频 | 九九精品视频一区二区三区 | 国产精品视频永久免费播放 | 毛片免费在线视频 | 日本一区二区三区免费看 | 亚洲国产精品综合久久2007 | 国产福利短视频 | 亚洲热线99精品视频 | 亚洲国产精品久久久久婷婷软件 | 奇米影视第四色首页 | 色婷婷久久综合中文久久一本` | 看大片全色黄大色黄 | 亚洲国产精品线观看不卡 | 久久www免费人成_看片美女图 |