Java Trie


  • 0
    C
    static class TrieNode{
            boolean isWord = false;
            TrieNode[] children;
            TrieNode(){
                children = new TrieNode[26];
            }
        }
        static class Trie{
            TrieNode root;
            Trie(){
                root = new TrieNode();
            }
            
            public void insert(String word) {
                TrieNode node = root;
                for(char c : word.toCharArray()){
                    if(node.children[c-'a'] == null){
                        node.children[c-'a'] = new TrieNode();
                    }
                    node = node.children[c-'a'];
                }
                node.isWord = true;
            }
            public boolean search(String word) {
                TrieNode node = root;
                for(char c : word.toCharArray()){
                    if(node.children[c-'a'] == null){
                        return false;
                    }
                    node = node.children[c-'a'];
                }
                return node.isWord;
            }
            public boolean startsWith(String prefix) {
                TrieNode node = root;
                for (char c : prefix.toCharArray()) {
                    if (node.children[c - 'a'] == null) return false;
                    node = node.children[c - 'a'];
                }
                return true;
            }
            
            
        }
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            Trie trie = new Trie();
            for(String s : words){
                trie.insert(s);
            }
            List<String> res = new ArrayList<>();
            
            for(String s : words){
                if(helper(trie,s,false)) res.add(s); 
            }
            return res;
        }
        private boolean helper(Trie trie, String s, boolean cut){
            if(s.equals("") && cut) return true;
            if(s.equals("")) return false;
            for(int i = 0; i < s.length(); i++){
                String pre = s.substring(0,i+1);
                if(i == s.length()-1 && !cut) return false;
                if(trie.search(pre)){
                    // cut = true;
                    if(helper(trie, s.substring(i+1), true)) return true;
                }
            }
            return false;
        }

Log in to reply
 

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