Java trie + dfs beats 92.61%


  • 0
    C

    Use trie to build the dictionary, then do dfs to search for longest path in the trie, while each node in the trie are word node.

    class Solution {
        class TrieNode {
            boolean isWord;
            TrieNode[] childs;
            TrieNode() {
                childs = new TrieNode[26];
            }
        }
        class Trie {
            TrieNode root;
            Trie() {
                root = new TrieNode();
            }
            
            public void addWord(String word) {
                TrieNode cur = root;
                for (int i = 0; i < word.length(); i++) {
                    int ind = word.charAt(i) - 'a';
                    if (cur.childs[ind] == null) {
                        cur.childs[ind] = new TrieNode();
                    }
                    cur = cur.childs[ind];
                }
                cur.isWord = true;
            }
        }
        
        public String longestWord(String[] words) {
            Trie trie = new Trie();
            for (String w : words) {
                trie.addWord(w);
            }
            String[] res = new String[] {""};
            dfs(trie.root, "", res);
            return res[0];
        }
        
        private void dfs(TrieNode root, String cur, String[] res) {
            if (root != null && root.isWord) {
                if (cur.length() > res[0].length()) {
                    res[0] = cur;
                }
            }
            for (int i = 0; i < root.childs.length; i++) {
                TrieNode c = root.childs[i];
                if (c != null && c.isWord) {
                    dfs(c, cur + (char)('a' + i), res);
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.