Accepted Java HashMap solution


  • 1
    class TrieNode {
      // Initialize your data structure here.
      char c;
      boolean isLeaf;
      Map<Character, TrieNode> children = new HashMap<Character, TrieNode>();
      
      public TrieNode() {}
      public TrieNode(char c) { this.c = c; }
    }
    
    public class Trie {
      private TrieNode root;
    
      public Trie() {
        root = new TrieNode();
      }
    
      // Inserts a word into the trie.
      public void insert(String word) {
        Map<Character, TrieNode> children = root.children;
        
        for (int i = 0; i < word.length(); i++) {
          char c = word.charAt(i);
          
          if (!children.containsKey(c))
            children.put(c, new TrieNode(c));
          
          TrieNode t = children.get(c);
          
          if (i == word.length() - 1) 
            t.isLeaf = true;
          
          children = t.children;
        }
      }
    
      // Returns if the word is in the trie.
      public boolean search(String word) {
          TrieNode t = searchLastNode(word);
          
          return t != null && t.isLeaf;
      }
    
      // Returns if there is any word in the trie
      // that starts with the given prefix.
      public boolean startsWith(String prefix) {
          return searchLastNode(prefix) != null;
      }
      
      // Returns the last TrieNode of word
      private TrieNode searchLastNode(String word) {
        Map<Character, TrieNode> children = root.children;
        
        for (int i = 0; i < word.length(); i++) {
          char c = word.charAt(i);
          
          if (!children.containsKey(c)) break;
              
          TrieNode t = children.get(c);
          
          if (i == word.length() - 1) 
            return t;
          
          children = t.children;
        }
        
        return null;
      }
    }

Log in to reply
 

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