Add and Search Word - Data structure design

LeetCode Q 211 - Add and Search Word - Data structure 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

Code:

class TrieNode {
	TrieNode[] children;
	boolean isEnd;
	public TrieNode () { this.children = new TrieNode[26]; }
}
    
TrieNode root;

// Initialize your data structure here.
public WordDictionary() {
	this.root = new TrieNode();
}
    
// Adds a word into the data structure. 
public void addWord(String word) {

	TrieNode node = root;

	for (char ch: word.toCharArray()) {
		if (node.children[ch - 'a'] == null) 
			node.children[ch - 'a'] = new TrieNode();
		node = node.children[ch - 'a']; 
	}

	node.isEnd = 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) {
	
	TrieNode node = root;

	for (int i = 0; i < word.length(); i++) {

		char ch = word.charAt(i);

		if (ch != '.') {
			if (node.children[ch - 'a'] == null) 
				return false;
			node = node.children[ch - 'a'];
		} else {
			for (int j = 0; j < 26; i++) {
				if (node.children[j] != null && 
					search(word.substring(0, i) + (char)(j + 'a') + word.substring(i + 1)))
					return true;
				}
			}
			return false;
		}
	}

	return node.isEnd;
}

We can realize the search method in another way.

code:

// 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 searchHelper(word, root, 0);
}

private boolean search(String word, TrieNode node, int index) {
	
	if (index == word.length()) return node.isEnd;

	char ch = word.charAt(index);

	if (ch != '.') {
		if (node.children[ch - 'a'] == null)
			return false;
		return search(word, node.children[ch - 'a'], index + 1);
	} else {
		for (int i = 0; i < 26; i++) {
			if (node.children[i] != null) {
				if (search(word, node.children[i], index + 1))
					return true;
			}
		}
		return false;
	}
}