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

🟠   🔖  深度优先搜索 设计 字典树 字符串  🔗 LeetCode

题目

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.

Example:

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

Constraints:

• 1 <= word.length <= 25
• word in addWord consists of lowercase English letters.
• word in search consist of '.' or lowercase English letters.
• There will be at most 2 dots in word for search queries.
• At most 10^4 calls will be made to addWord and search.

题目大意

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

实现词典类 WordDictionary ：

• WordDictionary() 初始化词典对象
• void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
• bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。

解题思路

关键点是，搜索可以包含正则表达式中的 .，代表任意一个字符。因此，通常的字符串匹配方式无法直接适用，应该用 字典树（Trie） 来设计。

1. 字典树 (Trie)：这是一个经典的数据结构，适合用于存储和检索字符串。字典树的每个节点代表一个字符，并且具有一个标记，用来判断是否到达一个完整的单词。
2. 递归搜索：在搜索时，如果遇到普通字符，沿着 Trie 进行普通的搜索；如果遇到 .，则需要递归地搜索当前节点的所有子节点，直到找到匹配的字符或最终没有匹配。

• addWord：O(m)，其中 m 是插入单词的长度。
• search：最坏情况下 O(n)，n 是字典树中所有节点的总数，因为 . 可能会触发对所有路径的遍历。

代码

var WordDictionary = function () {
	this.root = {}; // 初始化字典树的根节点
};

// 添加单词到字典树
/**
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function (word) {
	let node = this.root;
	for (let char of word) {
		// 如果当前字符不存在，则创建一个新节点
		if (!node[char]) {
			node[char] = {};
		}
		node = node[char]; // 移动到下一个节点
	}
	node.isEnd = true; // 单词结束标记
};

// 搜索单词，支持 . 通配符
/**
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function (word) {
	// 定义一个递归搜索函数
	const dfs = (node, i) => {
		// 如果到达了单词末尾，检查是否是一个完整的单词
		if (i == word.length) {
			return node.isEnd == true;
		}
		const char = word[i];
		// 如果遇到 .，递归地搜索所有子节点
		if (char === '.') {
			for (let key in node) {
				if (key !== 'isEnd' && dfs(node[key], i + 1)) {
					return true;
				}
			}
			return false;
		} else {
			// 如果是普通字符，沿着字典树继续搜索
			// 如果路径不存在，返回 false
			if (!node[char]) {
				return false;
			}
			// 否则，继续搜索下一个字符
			return dfs(node[char], i + 1);
		}
	};

	// 从根节点开始搜索
	return dfs(this.root, 0);
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * var obj = new WordDictionary()
 * obj.addWord(word)
 * var param_2 = obj.search(word)
 */

相关题目

题号	标题	题解	标签	难度
208	实现 Trie (前缀树)	[✓]	设计 字典树 哈希表 1+
745	前缀和后缀搜索		设计 字典树 数组 2+
2301	替换字符后匹配		数组 哈希表 字符串 1+
2416	字符串的前缀分数和	[✓]	字典树 数组 字符串 1+
3042	统计前后缀下标对 I		字典树 数组 字符串 3+
3045	统计前后缀下标对 II		字典树 数组 字符串 3+