Trie Tree recursion Java Solution


  • 0
    S
    public class WordDictionary {
    	Node root;
    	
    	WordDictionary(){
    		root = new Node();
    	}
    	
        // Adds a word into the data structure.
        public void addWord(String word) {
        	Node node = root;
            for(int i=0;i<word.length();i++){
            	char ch = word.charAt(i);
            	node = node.insert(node, ch);
            }
            node.isEnd = 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) {
            if(word.length() == 0)	return false;
            
            return searchFromNode(root, word);
        }
        
        private boolean searchFromNode(Node node, String word){
        	if(word.length() == 1){
        		char ch = word.charAt(0);
        		if(ch == '.'){
        			if(node.child.isEmpty())	
        				return false;
        			else{
        				Iterator iter = node.child.entrySet().iterator();
        				while(iter.hasNext()){
        					Map.Entry<Character, Node> entry = (Map.Entry)iter.next();
        					if(entry.getValue().isEnd)	return true;
        				}
        				return false;
        			}
        		}	
        		else{
        			if(node.child.containsKey(ch)){
        				Node newNode = (Node)node.child.get(ch);
        				return newNode.isEnd;
        			}else	return false;
        		}
        		
        	}
        	
        	char ch = word.charAt(0);
        	if(ch == '.'){
        		Iterator iter = node.child.entrySet().iterator();
        		while(iter.hasNext()){
        			Map.Entry<Character, Node> entry = (Map.Entry)iter.next();
        			if(searchFromNode((Node)entry.getValue(), word.substring(1)))
        				return true;
        		}
        		return false;
        	}
        	
        	if(node.child.containsKey(ch)){
        		return searchFromNode((Node)node.child.get(ch), word.substring(1));
        	}else return false;
        }
        
        class Node{
        	char ch;
        	boolean isEnd;
        	Map child;
        	
        	Node(char ch){
        		this.ch = ch;
        		child = new HashMap<Character,Node>();
        		isEnd = false;
        	}
        	
        	Node(){
        		this.ch = ' ';
        		child = new HashMap<Character,Node>();
        		isEnd = false;
        	}
        	
        	public Node insert(Node node, char ch){
        		if(node.child.containsKey(ch))
        			return (Node)node.child.get(ch);
        		else{
        			Node newNode = new Node(ch);
        			node.child.put(ch, newNode);
        			return newNode;
        		}
        	}
        }
    }

Log in to reply
 

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