Trie 是一颗非典型的多叉树模型。
前缀树
struct TrieNode {
bool isEnd; //该结点是否是一个串的结束
TrieNode* next[26]; //字母映射表
};
TrieNode* next[26]中保存了对当前结点而言下一个可能出现的所有字符的链接，因此我们可以通过一个父结点来预知它所有子结点的值：
for (int i = 0; i < 26; i++) {
char ch = 'a' + i;
if (parentNode->next[i] == NULL) {
//说明父结点的后一个字母不可为 ch
} else {
// 说明父结点的后一个字母可以是 ch
}
}
代码实现：
class Trie {
private:
bool isEnd;
Trie* next[26];//定义类
public:
Trie() {
isEnd = false;
memset(next, 0, sizeof(next));//初始化内存方式，头文件#include <string.h>
}
/*首先从根结点的子结点开始与 word 第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，
这时开始不断开辟新的结点，直到插入完 word 的最后一个字符，
同时还要将最后一个结点isEnd = true;，表示它是一个单词的末尾.*/
void insert(string word) {
Trie* node = this;
for (char c : word) {
if (node->next[c-'a'] == NULL) {
node->next[c-'a'] = new Trie();
}
node = node->next[c-'a'];
}
node->isEnd = true;
}
/*从根结点的子结点开始，一直向下匹配即可，如果出现结点值为空就返回false，如果匹配到了最后一个字符，那我们只需判断node->isEnd即可。*/
bool search(string word) {
Trie* node = this;
for (char c : word) {
node = node->next[c - 'a'];
if (node == NULL) {
return false;
}
}
return node->isEnd;
}
/*和 search 操作类似，只是不需要判断最后一个字符结点的isEnd，因为既然能匹配到最后一个字符，那后面一定有单词是以它为前缀的。*/
bool startsWith(string prefix) {
Trie* node = this;
for (char c : prefix) {
node = node->next[c-'a'];
if (node == NULL) {
return false;
}
}
return true;
}
};
总结：
- 形状唯一。与插入顺序和删除顺序无关。
- 查找与Trie 中包含多少个单词无关。都是单词长度L+1次。
- 耗费空间，如果 Trie 的高度为 n，字母表的大小为 m，最坏的情况是 Trie 中还不存在前缀相同的单词，那空间复杂度就为 O(m^n)。
一次建树，多次查询。
class WordDictionary {
public:
bool isEnd;
WordDictionary* next[26];
/** Initialize your data structure here. */
WordDictionary() {
isEnd = false;
memset(next, 0, sizeof(next));
}
/** Adds a word into the data structure. */
void addWord(string word) {
WordDictionary* p = this;
for(auto c : word) {
if(p->next[c-'a'] == nullptr)
p->next[c-'a'] = new WordDictionary();
p = p->next[c-'a'];
}
p->isEnd = 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 searchWord(this, word);
}
bool searchWord(WordDictionary* node, string word) {
if(word.size()==1) { //边界
if(isalpha(word[0])) {
if(node->next[word[0]-'a'] && node->next[word[0]-'a']->isEnd)
return true;
return false;
}
else {
for(int i=0; i<26; i++)
if(node->next[i] && node->next[i]->isEnd)
return true;
return false;
}
}
else {
if(isalpha(word[0])) {
if(node->next[word[0]-'a'])
return searchWord(node->next[word[0]-'a'], word.substr(1, word.size()-1));
else
return false;
}
else {
bool b;
for(int i=0; i<26; i++) {
if(node->next[i]){
b = searchWord(node->next[i], word.substr(1, word.size()-1));
if(b) 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);
*/
class TrieNode{
public:
string word = "";
vector<TrieNode*> nodes;
TrieNode():nodes(26, 0){}
};
class Solution {
int rows, cols;
vector<string> res;
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
rows = board.size();
cols = rows ? board[0].size():0;
if(rows==0 || cols==0) return res;
//建立字典树的模板
TrieNode* root = new TrieNode();
for(string word:words){
TrieNode *cur = root;
for(int i=0; i<word.size(); ++i){
int idx = word[i]-'a';
if(cur->nodes[idx]==0) cur->nodes[idx] = new TrieNode();
cur = cur->nodes[idx];
}
cur->word = word;
}
//DFS模板
for(int i=0; i<rows; ++i){
for(int j=0; j<cols; ++j){
dfs(board, root, i, j);
}
}
return res;
}
void dfs(vector<vector<char>>& board, TrieNode* root, int x, int y){
char c = board[x][y];
//递归边界
if(c=='.' || root->nodes[c-'a']==0) return;
root = root->nodes[c-'a'];
if(root->word!=""){
res.push_back(root->word);
root->word = "";
}
board[x][y] = '.';
if(x>0) dfs(board, root, x-1, y);
if(y>0) dfs(board, root, x, y-1);
if(x+1<rows) dfs(board, root, x+1, y);
if(y+1<cols) dfs(board, root, x, y+1);
board[x][y] = c;
}
};
