struct TrieNode{
bool is_end;//判断是否是尾节点
string word;//如果是尾节点，存储整个单词
TrieNode* kids[26];//儿子们
TrieNode(){
for(int i = 0; i < 26; ++i) { kids[i] = NULL; }
is_end = false;
}
~TrieNode(){//删除节点
for(int i = 0; i < 26; ++i) {
if(kids[i] != NULL) {
delete kids[i];
}
}
}
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
auto cp = root;//备份
for(int i = 0; i < word.size(); ++i){
int idx = word[i]-'a';//获取当前出入字母的下标
if(cp->kids[idx] == NULL){//没有该单词
cp->kids[idx] = new TrieNode();//创建节点，表示生成该单词
}
cp = cp->kids[idx];//更新节点
}
cp->is_end = true;//最后一个节点，标志单词结束
cp->word = word;//记录当前的单词
}
bool search(string word) {
auto cp = root;
for(int i = 0; i < word.length(); ++i){
int idx = word[i]-'a';
if(cp->kids[idx] == NULL) return false;
cp = cp->kids[idx];//更新节点，指向下一个
}
if(cp->is_end) return true;//查询到最后一个字母，如果是单词结尾，表示有该单词
return false;//没有结尾标记，说明没有该单词
}
bool startsWith(string prefix) {
auto cp = root;
for(int i = 0; i < prefix.length(); ++i){
int idx = prefix[i]-'a';
if(cp->kids[idx] == NULL) return false;
cp = cp->kids[idx];
}
return true;
}
private:
TrieNode* root;
};
思路
- insert
- 如果当前root节点的子节点含有字母x，那么就以x为新的root，判断是否存在下一个字母
- 如果不含有字母x，则创建新节点，然后以新添加的节点为新的root节点，继续判断
- 所有字母添加完成后，添加结束标记，并记录当前单词
- search
- 过程类似insert，不过如果不存在字母x，返回false
- 全部遍历完成后，如果没有发现结束标记，那么表示该单词是别的单词的一个前缀，树中不存在该单词。返回fasle
- startWith
- 过程类似search，如果不存在字母x，返回fasle
- 无需考虑是否有结束标记
struct Trie{
bool is_end;
Trie* kids[26];
Trie(){ for(int x = 0; x < 26; ++x) kids[x] = NULL; is_end = false;}
};
class Solution {
public:
Solution(){ root = new Trie(); }
vector findAllConcatenatedWordsInADict(vector& words) {
vector ans;
sort(words.begin(),words.end(),[](string a, string b){return a.length()//循环遍历每个单词
if(words[i].empty()) continue;
if(dfs(words[i],0)){//判断是否为合成词
ans.emplace_back(words[i]);
}else
insert(words[i]);//插入字典树
}
return ans;
}
private:
bool dfs(string& word, int start){
if(start == word.length()){ return true; }//全部找完
auto cp = root;//从头开始寻找
for(int i = start; i < word.length(); ++i){
int idx = word[i]-'a';//确定当前字母所在下标
cp = cp->kids[idx];//更新当前指针
if(cp == NULL) {
return false;
}
if(cp->is_end == true) {
if(dfs(word, i+1))//如果之后的单词能够组成连接词，那么直接返回true.否则重新for循环，判断下一个字母组成的单词是否满足连接词
return true;
}
}
return false;
}
void insert(string word){
auto cp = root;//保存root节点
for(int i = 0; i < word.length(); ++i) {
int idx = word[i] - 'a';//获取单词字母下标
if(cp->kids[idx] == NULL) {
cp->kids[idx] = new Trie();
}
cp = cp->kids[idx];
}
cp->is_end = true;//标志尾节点
}
private:
Trie* root;
};
思路
要判断单词word是否是连接词，我们可以遍历所有的单词，如果存在某个单词是是word的前缀，那么截断word，以剩下的subword为基础，遍历所有单词，寻找前缀。循环，直到找不到某个单词作为前缀，或者word被截断完。前者对应false，（该单词不是连接词），后者对应true,（该单词是连接词）。
but，每一次判断前缀都需要遍历所有单词，很明显，不划算。我们可以减少遍历的量嘛?当然可以
我们发现，连接词一定是大于组成连接词的子单词，所以，我们可以对words排序，对于某个单词word，只需遍历长度比他小的即可。
but，这样顺序遍历任然有很大的时间消耗。如果某个前缀在1000的下标，那么我们需要遍历0~999这些没有的单词。有木有什么办法解决这种浪费？当然有——前缀树
通过树的数据结构，以每一个字母为节点，分出26个分支，指向其他字母。字母按行展开，极大的减少遍历所耗费的时间。我们可以认为字母的存储是用hash表存储，那么所搜时间就是O(1)，极大的提高搜索效率。匹配单词的实质就是匹配字母。只要字母匹配的上，那么单词就能匹配上。
解法
比较操蛋的点是dfs遍历前缀树
递归：在word中寻找字母。
- 如果前缀树中的字母和word中的匹配，并且是结尾，那么表示树中存在该单词。从root节点递归寻找新字母
- 如果前缀树中的字母没有和word中的匹配，返回false，并从上一个节点（上一个单词的结尾）开始重新往下寻找。
struct Trie{
bool is_end;
Trie* kids[26];
Trie(){ for(int x = 0; x < 26; ++x) kids[x] = NULL; is_end = false;}
};
class Solution {
public:
Solution(){ root = new Trie(); }
string longestWord(vector& words) {
vector ans;
sort(words.begin(),words.end(),[](string a, string b){return a.length()//循环遍历每个单词
if(words[i].empty()) continue;
if(dfs(words[i],0)){//判断是否为合成词
ans.emplace_back(words[i]);
}else
insert(words[i]);//插入字典树
}
sort(ans.begin(),ans.end(),[](auto a, auto b) {
if(a.length() != b.length()) return a.length() > b.length();
else return a[0] < b[0];
}
);
if(ans.size()!=0){
return ans[0];
}
return "";
}
private:
bool dfs(string& word, int start){
if(start == word.length()){ return true; }//全部找完
auto cp = root;//从头开始寻找
for(int i = start; i < word.length(); ++i){
int idx = word[i]-'a';//确定当前字母所在下标
cp = cp->kids[idx];//更新当前指针
if(cp == NULL) {
return false;
}
if(cp->is_end == true) {
if(dfs(word, i+1))//如果之后的单词能够组成连接词，那么直接返回true.否则重新for循环，判断下一个字母组成的单词是否满足连接词
return true;
}
}
return false;
}
void insert(string word){
auto cp = root;//保存root节点
for(int i = 0; i < word.length(); ++i) {
int idx = word[i] - 'a';//获取单词字母下标
if(cp->kids[idx] == NULL) {
cp->kids[idx] = new Trie();
}
cp = cp->kids[idx];
}
cp->is_end = true;//标志尾节点
}
private:
Trie* root;
};
思路
基本就是上题的模板
