Leetcode 211. 添加与搜索单词 - 数据结构设计 解题思路及C++实现

解题思路：

用字典树来作为存储的数据结构。

新增单词的时候，就使用字典树插入新单词的方法，与LeetCode 208 题一样。

在查找某一个字典树时，使用深度优先搜索即可。

 

class WordDictionary { public://定义字典树中每个节点的结构struct Node{bool isword = false; //用于标记当前节点是否为单词的最后一个字符Node* next[27] = {};};Node* root; //每一个class都有一棵字典树/** Initialize your data structure here. */WordDictionary() {root = new Node(); //新建一棵字典树}/** Adds a word into the data structure. */void addWord(string word) {Node* tmp = root;for(auto w: word){if(tmp->next[w - 'a'] == NULL){ //还没有这个节点Node* tt = new Node();tmp->next[w - 'a'] = tt; //那就新建节点}tmp = tmp->next[w - 'a'];}tmp->isword = true; //遍历完一个单词}/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */bool search(string word) {return dfs(word, root, 0);}bool dfs(string word, Node* root, int i){if(!root) return false;if(i >= word.size()) return root->isword; //看看是不是一个完整的单词if(word[i] != '.'){if(root->next[word[i] - 'a']){return dfs(word, root->next[word[i] - 'a'], i+1);}else return false;}for(auto t: root->next){if(t){if(dfs(word, t, i+1)) return true;}}return false;} };/*** Your WordDictionary object will be instantiated and called as such:* WordDictionary* obj = new WordDictionary();* obj->addWord(word);* bool param_2 = obj->search(word);*/

 

 

 

总结

以上是生活随笔为你收集整理的Leetcode 211. 添加与搜索单词 - 数据结构设计 解题思路及C++实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。