Interview Classic 150 Questions P211 Add and Search Word - Data Structure Design

---

Timeline

Timeline

2025-11-24

init

Trie

---

Problem:

Add and Search Word - Data Structure Design

https://leetcode.cn/problems/design-add-and-search-words-data-structure/description/?envType=study-plan-v2&envId=top-interview-150

Recursive implementation, ifword[i]is a wildcard ‘.’, then start from all child nodes of the current Trie node and searchword.substr(i+1, n-i-1), and whenword[i]=='.'andi==n-1when, at this time it is the last node, the last node is a wildcard, so we only need to check whether the current node’s children containis_end==trueof

#include <string>
#include <vector>
using std::string;
using std::vector;

typedef struct TrieNode {
	vector<struct TrieNode *> children;
	int data;
	bool is_end;
} TrieNode;

class WordDictionary {
    private:
	TrieNode *root;

    public:
	WordDictionary()
	{
		root = new TrieNode;
		root->children = vector<struct TrieNode *>(26, nullptr);
		root->is_end = false;
	}

	void addWord(string word)
	{
		TrieNode *p = root, *node;
		int i = 0, n = word.size();
		int curr;
		for (i = 0; i < n; i++) {
			curr = word[i] - 'a';
			if (p->children[curr] != nullptr) {
				p = p->children[curr];
				continue;
			}
			node = new TrieNode;
			node->children = vector<struct TrieNode *>(26, nullptr);
			node->data = curr;
			node->is_end = false;
			p->children[curr] = node;
			p = node;
		}
		p->is_end = true;
	}
	bool searchImpl(string word, TrieNode *root)
	{
		TrieNode *p = root;
		int i = 0, n = word.size(), curr;
		for (i = 0; i < n; i++) {
			if (word[i] != '.') {
				curr = word[i] - 'a';
				if (p->children[curr] != nullptr) {
					p = p->children[curr];
					continue;
				}
				return false;

			} else {
				for (TrieNode *child : p->children) {
					if (child == nullptr) {
						continue;
					}
					if (i == n - 1 && child->is_end) {
						return true;
					}
					if (searchImpl(word.substr(i + 1, n - i - 1), child)) {
						return true;
					}
				}
				return false;
			}
		}

		return p->is_end;
	}
	bool search(string word)
	{
		return searchImpl(word, root);
	}
};

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