LeetCode Q211: 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.

For 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:

Design and implement a prefix tree (Trie)

	class WordDictionary {
	public:
	class TrieNode {
	public:
	// Initialize your data structure here.
	TrieNode() {
	wordsEndHere=false;
	memset(subTries, NULL, sizeof(subTries));
	}
	TrieNode(char _c): c(_c){
	wordsEndHere=false;
	memset(subTries, NULL, sizeof(subTries));
	}
	char c;
	bool wordsEndHere;
	TrieNode* subTries[26];
	};
	WordDictionary(){
	root = new TrieNode();
	}
	// Adds a word into the data structure.
	void addWord(string word) {
	TrieNode* p = root;
	for(int i=0; i<word.length(); i++){
	int c=word[i]-'a';
	if(p->subTries[c]==NULL){
	TrieNode * node = new TrieNode(c);
	p->subTries[c]=node;
	}
	p=p->subTries[c];
	}
	p->wordsEndHere=true;
	}
	// Returns if the word is in the data structure. A word could
	// contain the dot character '.' to represent any one letter.
	bool helper(TrieNode* root, string word){
	bool found=false;
	if(word.length()==0)
	return root->wordsEndHere;
	if(word[0]=='.'){
	for(int i=0; i<26; i++)
	if(root->subTries[i]!=NULL)
	found = found | helper(root->subTries[i], word.substr(1, word.length()-1));
	}else{
	int c = word[0]-'a';
	if(root->subTries[c]!=NULL)
	found = helper(root->subTries[c], word.substr(1, word.length()-1));
	}
	return found;
	}
	bool search(string word) {
	bool found=false;
	TrieNode* p =root;
	if(word.length()==0)
	return false;
	found = helper(p, word);
	return found;
	}
	TrieNode* root;
	};
	// Your WordDictionary object will be instantiated and called as such:
	// WordDictionary wordDictionary;
	// wordDictionary.addWord("word");
	// wordDictionary.search("pattern");

view raw Q211AddandSearchWordDataStructureDesign.cpp hosted with ❤ by GitHub