面试经典150题 P211 添加与搜索单词 - 数据结构设计

---

时间轴

时间轴

2025-11-24

init

Trie

---

题目：

添加与搜索单词 - 数据结构设计

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

递归实现，如果word[i]是通配符’.',则从当前 Trie 结点所有子结点开始，搜索word.substr(i+1, n-i-1),而当word[i]=='.'并且i==n-1时，此时是最后一个结点，最后一个结点为通配符，因此只需要判断当前结点的 children 中有没有is_end==true的

#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);
 */