LeetCode刷题实战211：添加与搜索单词 / 四六文摘

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 添加与搜索单词，我们先来看题面：

https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/

Design a data structure that supports adding new words and finding if a string matches any previously added string.

题意

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

实现词典类 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"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

提示：
1 <= word.length <= 500
addWord 中的 word 由小写英文字母组成
search 中的 word 由 '.' 或小写英文字母组成
最多调用 50000 次 addWord 和 search

解题

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

新增单词的时候，就使用字典树插入新单词的方法。

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

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;
}
};