Easy JAVA solution


  • 0
    S
    public class WordDictionary {
    
        public class TrieNode
        {
            Map<Character, TrieNode> map = new HashMap();
            boolean isLeaf = false;
        }
        
        TrieNode root;
        
        public WordDictionary()
        {
            root = new TrieNode();
        }
        // Adds a word into the data structure.
        public void addWord(String word) {
            TrieNode current = root;
            
            for(int i=0;i<word.length();i++)
            {
                Character c = word.charAt(i);
                
                if(current.map.containsKey(c))
                {
                    current = current.map.get(c);
                }
                else
                {
                    TrieNode newnode = new TrieNode();
                    current.map.put(c,newnode);
                    current = newnode;
                }
                if(i==word.length()-1)
                    current.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 searchDFS(word,0,root);
            
        }
        
        private boolean searchDFS(String word, int pos, TrieNode node)
        {
            if(pos==word.length())
                return node.isLeaf;
                
                
            Character c = word.charAt(pos);
            
            for(Map.Entry<Character,TrieNode> entry: node.map.entrySet())
            {
                Character triech = entry.getKey();
                TrieNode trienode = entry.getValue();
                
                if(c==triech||c=='.')
                {
                    if(searchDFS(word,pos+1,trienode))
                        return true;
                }
                
            }
            
            return false;
        }
    }

Log in to reply
 

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