Java Trie DFS+BFS


  • 1
    J

    DFS

    public class WordDictionary {
        TreeNode root = new TreeNode();
        // Adds a word into the data structure.
        public void addWord(String word) {
            TreeNode node = root;
            for(int i=0;i<word.length();i++){
                char cur = word.charAt(i);
                if(node.children[cur-'a']==null){
                    node.children[cur-'a'] = new TreeNode();
                }
                node = node.children[cur-'a'];
                if(i==word.length()-1) node.isLeaf = true;
            }
            
        }
    
        // Returns if the word is in the data structure. A word could
        // contain the dot character '.' to represent any one letter.
        public boolean search(String word) {
            return dfs(word,0,root);
        }
        
        public boolean dfs(String word, int index, TreeNode node){
            if(node==null) return false;
            
            int len = word.length();
            char cur = word.charAt(index);
            if(cur!='.'){
                TreeNode nxt = node.children[cur-'a'];
                if(nxt==null) return false;
                else if(index==len-1) return nxt.isLeaf;
                return dfs(word,index+1,nxt);
            } else {
                for(TreeNode n:node.children){
                    if(n!=null){
                        if(index==len-1&&n.isLeaf) return true;
                        if(index<len-1&&dfs(word,index+1,n)) return true;
                    }
                }
            }
            return false;
        }
    }
    class TreeNode{
        TreeNode[] children;
        boolean isLeaf;
        public TreeNode(){
            this.children = new TreeNode[26];
            this.isLeaf = false;
        }
    }
    

    BFS

    public class WordDictionary {
        TreeNode root = new TreeNode();
        // Adds a word into the data structure.
        public void addWord(String word) {
            TreeNode node = root;
            for(int i=0;i<word.length();i++){
                char cur = word.charAt(i);
                if(node.children[cur-'a']==null){
                    node.children[cur-'a'] = new TreeNode();
                }
                node = node.children[cur-'a'];
                if(i==word.length()-1) node.isLeaf = true;
            }
            
        }
    
        // Returns if the word is in the data structure. A word could
        // contain the dot character '.' to represent any one letter.
        public boolean search(String word) {
            TreeNode node = root;
            Queue<TreeNode> q = new LinkedList<> ();
            q.offer(node);
            
            for(int i=0;i<word.length();i++){
                char c = word.charAt(i);
                
                int size = q.size();
                
                while(size-->0){
                    TreeNode n = q.poll();
                    TreeNode[] child = n.children;
                    if(c!='.'){
                        TreeNode nxt = child[c-'a'];
                        if(nxt!=null) {
                            if(i==word.length()-1&&nxt.isLeaf) return true;
                            q.offer(nxt);
                        }
                    } else {
                        for(TreeNode nxt:child){
                            if(nxt!=null){
                                if(i==word.length()-1&&nxt.isLeaf) return true;
                                q.offer(nxt);
                            }
                        }
                    }
                }
                
            }
            return false;
        }
    }
    class TreeNode{
        TreeNode[] children;
        boolean isLeaf;
        public TreeNode(){
            this.children = new TreeNode[26];
            this.isLeaf = false;
        }
    }
    

Log in to reply
 

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