今天在LeetCode上看到一题
单词搜索II
给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例:
输入:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
输出: ["eat","oath"]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
简单地说就是给定一组单词，一组由字符构成的二维数组，然后在其中找出现过的单词
en..这个，一开始我的脑子里只有回溯哦，但是这种题用纯回溯不是送人头吗
回溯一时爽，超时火葬场
因此觉着这种题肯定有特定解法
打开官方题解就瞄到有人提到前缀树这种东西，我想可能是自己缺乏某些数据结构的基础知识了，于是点进了前缀树的专业入门题
嗯？等等，刚刚那题单词搜索II的难度是困难？
打扰了
那让我们来看看这题前缀树入门题
前缀树
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
看了网上有关前缀树的介绍
大致明白了
既然是树结构，肯定有根节点
这个根节点代表一切的开始
然后，从根节点开始，往外延伸定义N个节点，在没有被实例化之前，这些节点都处于NULL状态,可以将其定义为指针数组
class Trie{
public:
Trie(){}
Trie *next[N] = {NULL};
然后我们借助insert操作，开始一步步剖析其结构与使用原理
① insert
我们以英文单词作为基本输入单位，第一个英文单词叫做abcdefg(住手，这根本不是英语单词)，插入前缀树，从当前实例化的根节点开始，定义索引指针current
Trie *current=this;
从头到尾扫描单词，并同时确定当前字符是否“存在”于前缀树中
这个存在的意思是
将单词字符处理成数字形式方便下标索引数组
int indexA=word[i]-'a';
随后在当前索引指针的next指针数组中查看下标为indexA的节点是否为空
- 如果为空，则为节点分配空间
- 如果不为空，则将索引指针设置为该节点
那如何确定一个单词的结尾呢？
考虑到ab,abc,abcd,abcde等拥有共同前缀的单词
这时我们可以在数据结构中设立一个标志来判断该节点是否是一个单词的结尾
class Trie{
public:
Trie(){}
Trie *next[N] = {NULL};
bool whether = false;
因此一旦一个单词结束扫描后最终索引指针落到某个节点上时，该节点的标志就设置为true
用图来表示的话如下（用画图画的，不喜勿喷，呜呜呜太难了）
黑色圈圈代表还未被分配空间的节点
红色圈圈为根节点
绿色圈圈代表已经分配空间的节点
蓝色圈圈代表已经分配空间的终结节点
介绍完大体思路后，insert方面的代码熟悉数据结构的大佬们就能很快写出来
这里代码是自己根据思路写出来的，仅供参考
C++
void insert(string word) {
Trie *current=this; //将索引指针定义为当前根节点
for(int i=0;i<word.length();i++) //从头到尾扫描字符串
{
int indexA=word[i]-'a'; //解析字符为int索引
if(!(current->next[indexA])) //如果对应下标的指针指向空的话，分配新空间
{
current->next[indexA] = new Trie();
current=current->next[indexA]; //分配完空间后将索引指针指向该节点
}
else {
current=current->next[indexA]; //否则直接将指针指向该节点(其实有点重复，这里写出来是为了展现流程)
}
}
current->whether=true; //将最后的索引指针的标志设为true
}
② search
又到了喜闻乐见的search环节，插入了若干个单词后，前缀树已经初步成型，这时候我们就要在其中进行搜索了，比如搜索一个单词是否在该前缀树中巴拉巴拉
同样，该操作从前缀树的根节点开始,同样建立一个索引指针
Trie *current=this;
随后同样是从头到尾扫描字符串
同样是查看当前的索引指针current的next指针数组中的对应下标的指针指向的内容是否为空
只不过，如果为空，就直接返回false了，为啥呢，因为当前字符不存在，这个单词就跟不可能存在于当前的前缀树中了
搜索abcd,如果a,b都已经完成搜索了，但是c没找到，那就没得玩了呀
终于费劲千辛万苦搜索到了终点，但这也并不意味着单词存在于前缀树中
还要查看当前位置的标志
社想一下,当前前缀树中存放单词policeman,但是没有存放police,如果缺乏标志的话，police明明不存在但是也判断为存在了，就会造成错误
废话写太多了，直接上代码更简洁
bool search(string word) {
Trie * current=this; //定义索引指针指向根节点
for(int i=0;i<word.length();i++) //从头到尾扫描数组
{
int indexA=word[i]-'a'; //定义索引
if(!current->next[indexA]) //如果对应下表的指针指向为空直接返回false
return false;
current=current->next[indexA];
}
if(!current->whether) //如果当前位置的whether下标为false的话，证明并不是一个单词的结尾，返回false
return false;
else return true; //返回true
}
将搜索算法稍微改动一下就变成了 前缀识别算法了，这里也不多阐述，直接上代码
prefix
bool startsWith(string prefix) {
Trie * current=this;
for(int i=0;i<prefix.length();i++)
{
int indexA=prefix[i]-'a';
if(!current->next[indexA])
return false;
current=current->next[indexA];
}
return true;
}
简单的说只要你从头到尾把单词扫描完了，就证明该单词可以前缀的形式存在于前缀树中，也许是单词本身，也许是单词的前缀
AC代码(C++)
class Trie {
public:
/** Initialize your data structure here. */
Trie() {
}
bool whether=false;
Trie *next[26]={NULL};
/** Inserts a word into the trie. */
void insert(string word) {
Trie *current=this;
for(int i=0;i<word.length();i++)
{
int indexA=word[i]-'a';
if(!(current->next[indexA]))
{
current->next[indexA] = new Trie();
current=current->next[indexA];
}
else {
current=current->next[indexA];
}
}
current->whether=true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
Trie * current=this;
for(int i=0;i<word.length();i++)
{
int indexA=word[i]-'a';
if(!current->next[indexA])
return false;
current=current->next[indexA];
}
if(!current->whether)
return false;
else return true;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
Trie * current=this;
for(int i=0;i<prefix.length();i++)
{
int indexA=prefix[i]-'a';
if(!current->next[indexA])
return false;
current=current->next[indexA];
}
return true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
结论
学会了一种新的数据结构！相信以后能用这种新的数据结构来解决更多问题
Q.E.D.
Comments | 0 条评论