涂鸦网站建设,怎样黑公司的网站,企业展厅设计哪些内容,网站建设模板制作前景一、题目
1、题目描述
请你设计一个数据结构#xff0c;支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary #xff1a;
WordDictionary() 初始化词典对象void addWord(word) 将 word 添加到数据结构中#xff0c;之后可以对它…一、题目
1、题目描述
请你设计一个数据结构支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary
WordDictionary() 初始化词典对象void addWord(word) 将 word 添加到数据结构中之后可以对它进行匹配bool search(word) 如果数据结构中存在字符串与 word 匹配则返回 true 否则返回 false 。word 中可能包含一些 . 每个 . 都可以表示任何一个字母。
示例
输入
[WordDictionary,addWord,addWord,addWord,search,search,search,search]
[[],[bad],[dad],[mad],[pad],[bad],[.ad],[b..]]
输出
[null,null,null,null,false,true,true,true]解释
WordDictionary wordDictionary new WordDictionary();
wordDictionary.addWord(bad);
wordDictionary.addWord(dad);
wordDictionary.addWord(mad);
wordDictionary.search(pad); // 返回 False
wordDictionary.search(bad); // 返回 True
wordDictionary.search(.ad); // 返回 True
wordDictionary.search(b..); // 返回 True提示
1 word.length 25addWord 中的 word 由小写英文字母组成search 中的 word 由 . 或小写英文字母组成最多调用 104 次 addWord 和 search
2、基础框架
class WordDictionary {
public:WordDictionary() {}void addWord(string word) {}bool search(string word) {}
};/*** Your WordDictionary object will be instantiated and called as such:* WordDictionary* obj new WordDictionary();* obj-addWord(word);* bool param_2 obj-search(word);*/3、原题链接
211. 添加与搜索单词 - 数据结构设计
二、解题报告
1、思路分析
主要思路同【Leetcode】208.实现Trie前缀树但是需要注意插入的时候只有小写字母字符而查找的时候有.和小写字母字符所以遇到 “.” 字符时所有子孩子非空的情况都要进行尝试。
2、时间复杂度
3、代码详解
class WordDictionary {
private:class Node {public:bool end;Node *childs[26];Node() : end(false) {memset(childs, 0, sizeof(childs));}};Node *root;//深度优先搜索bool pathSearch(string word, Node *root, int index) {if (index word.size()) {return root-end;}Node *node root;int path 0;if (word[index] .) { //字符.for (int i 0; i 26; i) { //所有非空的孩子都要尝试if (node-childs[i]) {bool res pathSearch(word, node-childs[i], index 1);if (res) return true;}}return false;} else { //字母字符path word[index] - a;if (node-childs[path] nullptr) {return false;}return pathSearch(word, node-childs[path], index 1);}}
public:WordDictionary() {root new Node();}void addWord(string word) {Node *node root;int path 0;for (int i 0; word[i]; i) {path word[i] - a;if (node-childs[path] nullptr) {node-childs[path] new Node();}node node-childs[path];}node-end true;}bool search(string word) {return pathSearch(word, root, 0);}
};/*** Your WordDictionary object will be instantiated and called as such:* WordDictionary* obj new WordDictionary();* obj-addWord(word);* bool param_2 obj-search(word);*/
