Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

Solution

Method 1 - Use Hashmap Based Trie

This problem is similar with Implement Trie. The solution 1 below uses the same definition of a trie node. To handle the “.” case for this problem, we need to search all possible paths, instead of one path.

Here is TrieNode from Map-based Trie Implementation:

1
2
3
4

class TrieNode {
	HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode> ();
	boolean isLeaf;
}

Here is WordDictionary:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class WordDictionary {
	private final TrieNode root = new TrieNode();  
	  
    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode curr = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!curr.children.containsKey(c)) {
                curr.children.put(c, new TrieNode());
            }
            curr = curr.children.get(c);
        }
        curr.isLeaf = 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 dfsSearch(word, root);
    }

    private boolean dfsSearch(String word, TrieNode node) {
        if (word == null || (word.isEmpty())) {
            return node.isLeaf;
        }
        char c = word.charAt(0);
        if (c == '.') {
            for (TrieNode child : node.children.values()) {
                if (dfsSearch(word.substring(1), child)) {
                    return true;
                }
            }
        }
        //if character is neither equal to the node nor '.', return false
        if (!node.children.containsKey(c)) {
            return false;
        }
        return dfsSearch(word.substring(1), node.children.get(c));
    }
}

Our search method is a bit heavy, as we are creating multiple substring of the word. here is a lighter method:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

private boolean dfsSearch(String word, int pos, TrieNode node) {
	if (pos == word.length()) {
		return node.isWord;
	}
	
	char c = word.charAt(pos);
	if (c == '.') {
		for (TrieNode child : node.children.values()) {
			if (dfsSearch(word, pos+1, child)) {
				return true;
			}
		}
		return false;
	}
	
	//if character at position 'pos' is neither equal to the node nor '.', return false
	if (!node.children.containsKey(word.charAt(pos))) {
		return false;
	}

	return dfsSearch(word, pos + 1, node.children.get(c));
}

Method 2 - Using Array Based Trie Instead of HashMap

We can also use Array-based Trie Implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

class TrieNode {
	TrieNode[] children;
	boolean isLeaf;

	public TrieNode() {
		children = new TrieNode[26];
	}
}

public class WordDictionary {
	private final TrieNode root;

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

	// Adds a word into the data structure.  
	public void addWord(String word) {
		TrieNode p = root;
		for (int i = 0; i<word.length(); i++) {
			char c = word.charAt(i);
			int index = c - 'a';
			if (p.children[index] == null) {
				TrieNode temp = new TrieNode();
				p.children[index] = temp;
			}
			p = p.children[index];
		}

		p.isLeaf = 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 dfsSearch(word, 0, root);
	}

	public boolean dfsSearch(String word, int pos, TrieNode p) {
		if (p.isLeaf && pos == word.length())
			return true;

		if (pos >= word.length())
			return false;

		char c = word.charAt(pos);

		if (c == '.') {
			for (TrieNode child: p.children) {
				if (child != null) {
					if (dfsSearch(word, pos + 1, child)) {
						return true;
					}
				}
			}
			return false;

		}
		int index = c - 'a';

		if (p.children[index] == null) {
			return false;
		}

		return dfsSearch(word, pos + 1, p.children[index]);
	}
}