208. Implement Trie (Prefix Tree).md

208. Implement Trie (Prefix Tree)

---

similar as leetcode Daily Challenge on June 30, 2020. 212. Word Search II

---

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note:

You may assume that all inputs are consist of lowercase letters a-z. All inputs are guaranteed to be non-empty strings.

---

Solution

• mine
  • Java

    • Runtime: 29 ms, faster than 97.66%,Memory Usage: 50.3 MB, less than 42.67% of Java online submissions

      public Trie[] childs;
      public boolean hasValue;
      
      public Trie() {
           childs = new Trie[26];
      }
      
      /** Inserts a word into the trie. */
      public void insert(String word) {
          Trie t = this;
          char[] arr = word.toCharArray();
          for(char c : arr){
              int i = c - 'a';
              if(t.childs[i] == null){
                  t.childs[i] = new Trie();
              }
              t = t.childs[i];
          }
          t.hasValue = true;
      }
      
      /** Returns if the word is in the trie. */
      public boolean search(String word) {
          Trie t = this;
          char[] arr = word.toCharArray();
          for(char c: arr){
              int i = c - 'a';
              if(t.childs[i] == null){
                  return false;
              }
              t = t.childs[i];
          }
          return t != null && t.hasValue;
      }
      
      /** Returns if there is any word in the trie that starts with the given prefix. */
      public boolean startsWith(String prefix) {
          Trie t = this;
          char[] arr = prefix.toCharArray();
          for(char c: arr){
              int i = c - 'a';
              if(t.childs[i] == null){
                  return false;
              }
              t = t.childs[i];
          }
          return true;
      }
      

    • HashMap Runtime: 76 ms, faster than 12.02%, Memory Usage: 67.2 MB, less than 5.00% of Java online submissions

      public HashMap<Integer, Trie> childs;
      public boolean hasValue;
      
      public Trie() {
          childs = new HashMap<>();
      }
      
      /**
       * Inserts a word into the trie.
       */
      public void insert(String word) {
          Trie t = this;
          char[] arr = word.toCharArray();
          for (char c : arr) {
              int i = c - 'a';
              if (!t.childs.containsKey(i)) {
                  t.childs.put(i, new Trie());
              }
              t = t.childs.get(i);
          }
          t.hasValue = true;
      }
      
      /**
       * Returns if the word is in the trie.
       */
      public boolean search(String word) {
          Trie t = this;
          char[] arr = word.toCharArray();
          for (char c : arr) {
              int i = c - 'a';
              if (!t.childs.containsKey(i)) {
                  return false;
              }
              t = t.childs.get(i);
          }
          return t != null && t.hasValue;
      }
      
      /**
       * Returns if there is any word in the trie that starts with the given prefix.
       */
      public boolean startsWith(String prefix) {
          Trie t = this;
          char[] arr = prefix.toCharArray();
          for (char c : arr) {
              int i = c - 'a';
              if (!t.childs.containsKey(i)) {
                  return false;
              }
              t = t.childs.get(i);
          }
          return true;
      }
      

---