Leetcode 211. Add and Search Word - Data structure design

Problem Explanation

This problem involves creating a data structure that stores words so that they can be searched later not just by the whole word, but also by a combination of letters and .s. Each . represents any possible letter. This means if you store the word "hello" in the data structure, you should be able to successfully find the word by searching "hello", but also by searching for "h.llo", "he.lo", ".e..o", etc.

For instance, let's consider an example:

We create an instance of the data structure and add "word".

addWord("word")

Now, the data structure contains "word". We can search for "word" in the following ways:

search("word") -> true search("w.rd") -> true search("wor.") -> true search(".o.d") -> true search("....") -> true

But we search for a word or pattern that doesn't exist, it should return false:

search("nope") -> false search("w.rd..") -> false search(".o.dz") -> false search(".....") -> false

Approach Explanation

To solve this problem, we can use a Trie, which is a tree-based data structure ideal for efficient word searches. The Trie represents each letter of a word as a node, with links to the next letters, creating a path through the tree for each word.

What's unique in this case is that when we encounter a . we don't follow a single path, instead, we branch out and follow all of the paths from that node onwards, as a . can represent any letter. This means we'd have to do a Depth First Search (DFS) through all the routes and return true as soon as we find a route that leads to a complete word.

Here's how the trie might look after adding "word":

1
2
3  root
4  /  \
5 'w'  .
6/  \
7'o'  .
8/  \
9'r'  .
10/  \
11'd'  .
12/
13null

So if we search '.o.d', the DFS will traverse from root to 'w', then 'o', 'r' and finally to 'd'.

Now let's implement this in different languages:

Python Solution

1
2python
3class TrieNode:
4    def __init__(self):
5        self.children = [None]*26
6        self.isWord = False
7
8
9class WordDictionary(object):
10
11    def __init__(self):
12        self.root = TrieNode()
13
14    def addWord(self, word):
15        node = self.root
16        for w in word:
17            if not node.children[ord(w) - ord('a')]:
18                node.children[ord(w) - ord('a')] = TrieNode()
19            node = node.children[ord(w) - ord('a')]
20        node.isWord = True
21
22    def search(self, word):
23        return self.dfs(self.root, word, 0)
24
25    def dfs(self, node, word, index):
26        if index == len(word):
27            return node.isWord
28        if word[index] != ".":
29            node = node.children[ord(word[index]) - ord('a')]
30            return node is not None and self.dfs(node, word, index + 1)
31        for child in node.children:
32            if child and self.dfs(child, word, index + 1):
33                return True
34        return False

TODO: Add C++, Java, JavaScript, C# Solutions.## JavaScript Solution The JavaScript solution would use a similar Trie approach. We will define two methods for the "WordDictionary" class, "addWord" and "search". Moreover, we will also define a helper function "dfs".

1
2javascript
3class TrieNode {
4    constructor() {
5      this.children = {};
6      this.isWord = false;
7    }
8}
9
10class WordDictionary {
11    constructor() {
12      this.root = new TrieNode();
13    }
14
15    addWord(word) {
16      let node = this.root;
17      for(let i = 0; i < word.length; i++) {
18        if(node.children[word[i]] === undefined)
19          node.children[word[i]] = new TrieNode();
20
21        node = node.children[word[i]];
22      }
23      node.isWord = true;
24    }
25
26    search(word, node = this.root, i = 0) {
27      if(i === word.length) return node.isWord;
28
29      if(word[i] === '.')
30        for(let child in node.children)
31          if(this.search(word, node.children[child], i + 1)) return true;
32
33      return (node.children[word[i]] !== undefined) &&
34              this.search(word, node.children[word[i]], i + 1);
35    }
36}

Java Solution

The Java solution will implement a nested TrieNode class within the WordDictionary class. We will also create addWord and search methods similar to our JavaScript and Python solutions.

1
2java
3public class WordDictionary {
4    private TrieNode root;
5
6    public WordDictionary() {
7        root = new TrieNode();
8    }
9
10    public void addWord(String word) {
11        TrieNode node = root;
12        for(char c : word.toCharArray()){
13            if(node.children[c - 'a'] == null){
14                node.children[c - 'a'] = new TrieNode();
15            }
16
17            node = node.children[c - 'a'];
18        }
19        node.isWord = true;
20    }
21
22    public boolean search(String word) {
23        return dfs(root, word, 0);
24    }
25
26    private boolean dfs(TrieNode node, String word, int index) {
27        if(index == word.length()) return node.isWord;
28        char c = word.charAt(index);
29
30        if(c != '.'){
31            if(node.children[c - 'a'] != null)
32                return dfs(node.children[c - 'a'], word, index + 1);
33            else return false;
34        }else{
35            for(int i = 0; i < 26; i++){
36                if(node.children[i] != null)
37                    if(dfs(node.children[i], word, index + 1)) return true;
38            }
39        }
40        return false;
41    }
42
43    class TrieNode {
44        public TrieNode[] children;
45        public boolean isWord;
46
47        public TrieNode() {
48            children = new TrieNode[26];
49            isWord = false;
50        }
51    }
52}

These solutions show the power of data structures in search algorithms. By using a Trie, we can store words and perform complex searches efficiently.