211. Add and Search Word - Data structure design.md

211. Add and Search Word - Data structure design

---

leetcode Daily Challenge on August 5th, 2020.

---

Difficulty : Medium

Related Topics : Backtracking、Trie、Design

---

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:

• You may assume that all words are consist of lowercase letters a-z.

---

Solution

• mine
  • Java

    • Trie Runtime: 36 ms, faster than 98.23%, Memory Usage: 50.5 MB, less than 33.72% of Java online submissions

      class WordDictionary {
          WordDictionary[] next;
          boolean hasValue;
      
          /**
           * Initialize your data structure here.
           */
          public WordDictionary() {
              next = new WordDictionary[26];
          }
      
          /**
           * Adds a word into the data structure.
           */
          public void addWord(String word) {
              char[] arr = word.toCharArray();
              WordDictionary t = this;
              for (char c : arr) {
                  if (t.next[c - 'a'] == null) {
                      t.next[c - 'a'] = new WordDictionary();
                  }
                  t = t.next[c - 'a'];
              }
              t.hasValue = 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 search(word.toCharArray(), 0);
          }
      
          public boolean search(char[] arr, int s) {
              WordDictionary t = this;
              for (int i = s; i < arr.length; i++) {
                  char c = arr[i];
                  if (c == '.') return check(t, arr, i);
                  if (t.next[c - 'a'] == null) {
                      return false;
                  }
                  t = t.next[c - 'a'];
              }
              return t.hasValue;
          }
      
          boolean check(WordDictionary t, char[] arr, int s) {
              for (WordDictionary i : t.next) {
                  if (i == null) continue;
                  if (i.search(arr, s + 1)) return true;
              }
              return false;
          }
      }
      

    • Regular Expression Runtime: 113 ms, faster than 11.65%, Memory Usage: 122.1 MB, less than 5.27% of Java online submissions

      import java.util.regex.Pattern;
      class WordDictionary {
      
          Map<Integer,HashSet<String>> map;
      
          /** Initialize your data structure here. */
          public WordDictionary() {
              map = new HashMap<>();
          }
      
          /** Adds a word into the data structure. */
          public void addWord(String word) {
              int n = word.length();
              HashSet<String> s = map.getOrDefault(n, new HashSet<>());
              s.add(word);
              map.put(n, s);
          }
      
          /** 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) {
              int n = word.length();
              HashSet<String> set = map.getOrDefault(n, new HashSet<>());
              if(word.contains(".")){
                  for(String s : set){
                      if(Pattern.matches(word, s)) return true;
                  }
                  return false;
              }else{
                  return set.contains(word);
              }
          }
      }
      

---

• the most votes

• Runtime: 73 ms, faster than 37.75%, Memory Usage: 78.2 MB, less than 5.27% of Java online submissions

  class WordDictionary {
      public class TrieNode {
          public TrieNode[] children = new TrieNode[26];
          public String item = "";
      }
  
      private TrieNode root = new TrieNode();
  
      public void addWord(String word) {
          TrieNode node = root;
          for (char c : word.toCharArray()) {
              if (node.children[c - 'a'] == null) {
                  node.children[c - 'a'] = new TrieNode();
              }
              node = node.children[c - 'a'];
          }
          node.item = word;
      }
  
      public boolean search(String word) {
          return match(word.toCharArray(), 0, root);
      }
  
      private boolean match(char[] chs, int k, TrieNode node) {
          if (k == chs.length) return !node.item.equals("");
          if (chs[k] != '.') {
              return node.children[chs[k] - 'a'] != null && match(chs, k + 1, node.children[chs[k] - 'a']);
          } else {
              for (int i = 0; i < node.children.length; i++) {
                  if (node.children[i] != null) {
                      if (match(chs, k + 1, node.children[i])) {
                          return true;
                      }
                  }
              }
          }
          return false;
      }
  }
  

---