Design Add and Search Words Data Structure

---

Design Add and Search Words Data Structure: Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.
• void addWord(word) Adds word to the data structure, it can be matched later.
• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example 1:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

---

Constraints:

• 1 <= word.length <= 25

---

Try this Problem on your own or check similar problems:

1. Implement Trie (Prefix Tree)
2. Prefix and Suffix Search

Solution:

Java

class WordDictionary {
  class Trie {
      private class TrieNode{
          TrieNode[] children;
          boolean isWord = false;
          public TrieNode(){
              children = new TrieNode[26];
          }
      }

      TrieNode root;
      public Trie() {
          root = new TrieNode();
      }

      public boolean search(String word){
          return dfs(word, root, 0);
      }

      private boolean dfs(String word, TrieNode root, int idx){
          if(root == null) return false;
          if(idx == word.length()) return root.isWord;

          char c = word.charAt(idx);
          boolean result = false;
          if(c == '.'){
              for(int i = 0; i < root.children.length; ++i){
                  if(root.children[i] != null && dfs(word, root.children[i], idx + 1)) return true;
              }
          }else{
              result |= dfs(word, root.children[c - 'a'], idx + 1);
          }
          return result;
      }

      public void insert(String word) {
          TrieNode iter = root, prevMatchAll = null, prev = null;
          for(int i = 0; i < word.length(); ++i){
              char letter = word.charAt(i);
              if(iter.children[letter - 'a'] == null){
                  iter.children[letter - 'a'] = new TrieNode();
              }
              iter = iter.children[letter - 'a'];
          }
          iter.isWord = true;
      }
  }

  Trie t;
  public WordDictionary() {
      t = new Trie();
  }

  public void addWord(String word) {
      t.insert(word);
  }

  public boolean search(String word) {
      return t.search(word);
  }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

JavaScript

var WordDictionary = function () {
  this.t = new Trie();
};

/**
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function (word) {
  this.t.insert(word);
};

/**
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function (word) {
  return this.t.search(word);
};

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  search(word) {
    return this.dfs(word, this.root, 0);
  }

  dfs(word, root, idx) {
    if (root === null) return false;
    if (idx === word.length) return root.isWord;

    const c = word.charAt(idx);
    let result = false;
    if (c === ".") {
      for (let i = 0; i < root.children.length; ++i) {
        if (
          root.children[i] !== null &&
          this.dfs(word, root.children[i], idx + 1)
        ) {
          return true;
        }
      }
    } else {
      result |= this.dfs(word, root.children[c.charCodeAt(0) - 97], idx + 1);
    }
    return result;
  }

  insert(word) {
    let iter = this.root;
    for (let i = 0; i < word.length; ++i) {
      const letter = word.charAt(i);
      if (iter.children[letter.charCodeAt(0) - 97] === null) {
        iter.children[letter.charCodeAt(0) - 97] = new TrieNode();
      }
      iter = iter.children[letter.charCodeAt(0) - 97];
    }
    iter.isWord = true;
  }
}

class TrieNode {
  constructor() {
    this.children = Array(26).fill(null);
    this.isWord = false;
  }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * var obj = new WordDictionary()
 * obj.addWord(word)
 * var param_2 = obj.search(word)
 */

Python

class WordDictionary:

    def __init__(self):
      self.t = Trie()


    def addWord(self, word: str) -> None:
      self.t.insert(word)


    def search(self, word: str) -> bool:
      return self.t.search(word)

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def search(self, word):
        return self.dfs(word, self.root, 0)

    def dfs(self, word, root, idx):
        if root is None:
            return False
        if idx == len(word):
            return root.isWord

        c = word[idx]
        result = False
        if c == '.':
            for i in range(len(root.children)):
                if root.children[i] and self.dfs(word, root.children[i], idx + 1):
                    return True
        else:
            result |= self.dfs(word, root.children[ord(c) - ord('a')], idx + 1)
        return result

    def insert(self, word):
        iter = self.root
        for letter in word:
            if not iter.children[ord(letter) - ord('a')]:
                iter.children[ord(letter) - ord('a')] = TrieNode()
            iter = iter.children[ord(letter) - ord('a')]
        iter.isWord = True


class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.isWord = False


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

C++

class TrieNode {
public:
    vector<TrieNode*> children;
    bool isWord;

    TrieNode() {
        children = vector<TrieNode*>(26, nullptr);
        isWord = false;
    }
};

class Trie {
public:
    TrieNode* root;

    Trie() {
        root = new TrieNode();
    }

    bool search(string word) {
        return dfs(word, root, 0);
    }

    bool dfs(string word, TrieNode* root, int idx) {
        if (root == nullptr)
            return false;
        if (idx == word.length())
            return root->isWord;

        char c = word[idx];
        bool result = false;
        if (c == '.') {
            for (int i = 0; i < root->children.size(); ++i) {
                if (root->children[i] && dfs(word, root->children[i], idx + 1)) {
                    return true;
                }
            }
        } else {
            result |= dfs(word, root->children[c - 'a'], idx + 1);
        }
        return result;
    }

    void insert(string word) {
        TrieNode* iter = root;
        for (char letter : word) {
            if (!iter->children[letter - 'a']) {
                iter->children[letter - 'a'] = new TrieNode();
            }
            iter = iter->children[letter - 'a'];
        }
        iter->isWord = true;
    }
};

class WordDictionary {
private:
    Trie t;
public:
    WordDictionary() {
      t = Trie();
    }

    void addWord(string word) {
      t.insert(word);
    }

    bool search(string word) {
      return t.search(word);
    }
};




/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

---

Time/Space Complexity:

• Time Complexity: O(W l + Qn) where W is the number of writes to the trie, while Q is number of reads. l is the average word length
• Space Complexity: O(nl) where n is the total number of nodes in the trie

---

Explanation:

We will have frequent word searches so trie seems like a natural choice for data structure. We utilize the implementation from Implement Trie (Prefix Tree) with a DFS search when searching for the word. For each letter we have two possibilities, it's either '.' and then we have to check every child of the current node or it's a lowercase letter and we just move to the node following the edge that matches that letter and continue our search. We have two base cases, first is root == null then we just return false, for the second case we reach the end of the word and we check if the current node is also a valid end of one of the inserted words in the trie root.isWord. Time complexity on insert word is proportional to the length of the string, while on search we have the worst time complexity of nl where nl is total number of nodes in the trie (number of words times the average length of the word).