本文主要是介绍CareerCup Trie Prefix Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Return a shortest prefix of <code>word</code> that is <em>not</em> a prefix of any word in the <code>list</code>
e.g.
word: cat, it has 4 prefixes: “”, “c”, “ca”, “cat”
list: alpha, beta, cotton, delta, camera
Result is “cat”
-----------------------------------------------------------------------------
Use unordered_map to replace array
#include <stdio.h>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <iostream>
using namespace std;class Trie
{public:int num;//to remember how many word can reach here,that is to say,prefixbool terminal;//If terminal==true ,the current point has no following pointunordered_map<char, Trie*> son;Trie(bool terminal = false, int num = 1):terminal(terminal), num(num){}
};
typedef unordered_map<char, Trie*>::iterator IT;
Trie* BuildTrie()// create a new node
{Trie *root=new Trie(false, 0);return root;
}
void Insert(Trie* root, string& s)// insert a new word to Trie tree
{++root->num;for(int i=0; i<s.length(); ++i){if (root->son.find(s[i]) == root->son.end()) {Trie* tmp = new Trie(false, 1);root->son.insert(make_pair(s[i],tmp));}elseroot->son[s[i]]->num++;root = root->son[s[i]];}root->terminal=true;
}
void Delete(Trie *root)// delete the whole tree
{if(root!=NULL) {for (IT it = root->son.begin(); it != root->son.end(); ++it) Delete(it->second);delete root; root=NULL;}
}
Trie* Find(Trie *root,string& s)//trie to find the current word
{for(int i=0;i<s.length();++i)if(root->son[s[i]]!=NULL)root=root->son[s[i]];else return NULL;return root;
}
void ListAll(Trie *root,string& cur)
{if (root->terminal)cout << cur << endl;for (IT it = root->son.begin(); it != root->son.end(); ++it) {string next = cur + it->first;ListAll(it->second, next);}
}void dfs(Trie* root, int K, string& cur, vector<string>& longeststr) {if (root->num < K)return;int ls = longeststr.size(), l0 = ls == 0 ? 0 : longeststr[0].length(), cl = cur.length();if (root->num == K) {if (ls == 0)longeststr.push_back(cur);else if (l0 < cl){longeststr.clear();longeststr.push_back(cur);}else if(l0 == cl)longeststr.push_back(cur);}for (IT it = root->son.begin(); it != root->son.end(); ++it) {string next = cur + it->first;if (it->second->num >= K)dfs(it->second, K, next, longeststr);}
}
vector<string> isExist(Trie *root, int K) {string cur = "";vector<string> longeststr;dfs(root, K, cur, longeststr);return longeststr;
}int main() {Trie* trie = BuildTrie();string str[] = {"abc", "ab", "ade", "dcef"};for (int i = 0; i < 4; ++i)Insert(trie, str[i]);string s = "ab";Trie *searchWord = Find(trie, s);ListAll(trie, s); vector<string> res = isExist(trie, 1);return 0;
}
------------------------------------------------------------------------------
Use array
#include <stdio.h>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
const int sonnum=26,base='a';
class Trie
{public:int num;//to remember how many word can reach here,that is to say,prefixbool terminal;//If terminal==true ,the current point has no following pointTrie *son[sonnum];//the following pointTrie(bool terminal = true, int num = 0):terminal(terminal), num(num){for (int i = 0; i < sonnum; ++i)son[i] = NULL;}
};
Trie* BuildTrie()// create a new node
{Trie *root=new Trie(true, 0);root->terminal = false;return root;
}
void Insert(Trie* root, string& s)// insert a new word to Trie tree
{for(int i=0; i<s.length(); ++i){if(root->son[s[i]-base] == NULL)root->son[s[i]-base]=new Trie();else root->son[s[i]-base]->num++;root->terminal = false;root=root->son[s[i]-base];}root->terminal=true;
}
void Delete(Trie *root)// delete the whole tree
{if(root!=NULL){for(int i=0;i<sonnum;++i)if(root->son[i]!=NULL)Delete(root->son[i]);delete root; root=NULL;}
}
Trie* Find(Trie *root,string& s)//trie to find the current word
{for(int i=0;i<s.length();++i)if(root->son[s[i]-base]!=NULL)root=root->son[s[i]-base];else return NULL;return root;
}
void ListAll(Trie *root,string& cur)
{if (root->terminal) {cout << cur;return;}else {for (int i = 0; i < sonnum; ++i)if (root->son[i]) { string tmp = "a";tmp[0] += i;string next = cur + tmp;ListAll(root->son[i], next); }}
}int main() {Trie* trie = BuildTrie();string str[] = {"abc", "ab", "ade", "ace"};for (int i = 0; i < 4; ++i)Insert(trie, str[i]);string s = "a";Trie *searchWord = Find(trie, s);ListAll(searchWord, s); return 0;
}The above code is not right:
#include <stdio.h>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
const int sonnum=26,base='a';
class Trie
{public:int num;//to remember how many word can reach here,that is to say,prefixbool terminal;//If terminal==true ,the current point has no following pointTrie *son[sonnum];//the following pointTrie(bool terminal = false, int num = 1):terminal(terminal), num(num){for (int i = 0; i < sonnum; ++i)son[i] = NULL;}
};
Trie* BuildTrie()// create a new node
{Trie *root=new Trie(false, 1);return root;
}
void Insert(Trie* root, string& s)// insert a new word to Trie tree
{for(int i=0; i<s.length(); ++i){if(root->son[s[i]-base] == NULL)root->son[s[i]-base]=new Trie(false,1);else root->son[s[i]-base]->num++;root=root->son[s[i]-base];}root->terminal=true;
}
void Delete(Trie *root)// delete the whole tree
{if(root!=NULL){for(int i=0;i<sonnum;++i)if(root->son[i]!=NULL)Delete(root->son[i]);delete root; root=NULL;}
}
Trie* Find(Trie *root,string& s)//trie to find the current word
{for(int i=0;i<s.length();++i)if(root->son[s[i]-base]!=NULL)root=root->son[s[i]-base];else return NULL;return root;
}
void ListAll(Trie *root,string& cur)
{if (root->terminal)cout << cur << endl;for (int i = 0; i < sonnum; ++i)if (root->son[i]) { string tmp = "a";tmp[0] += i;string next = cur + tmp;ListAll(root->son[i], next); }
}int main() {Trie* trie = BuildTrie();string str[] = {"abc", "ab", "ade", "ace"};for (int i = 0; i < 4; ++i)Insert(trie, str[i]);string s = "ab";Trie *searchWord = Find(trie, s);ListAll(searchWord, s); return 0;
}Python Version:
class Node:def __init__(self, terminal = False, num = 0):self.terminal = Falseself.num = numself.son = {}def BuildTrie():root = Node(False, 0)return rootdef Insert(root, s):root.num += 1for c in s:if (c in root.son):root = root.son[c]root.num += 1else:root.son[c] = Node(False, 1)root = root.son[c]root.terminal = Truedef IsExist(root, s):for c in s:if (c in root.son):root = root.son[c]else:return Falsereturn root.terminalif __name__ == '__main__':root = BuildTrie()for item in ["abc", "ab", "ade", "ace"]:Insert(root, item)print(IsExist(root, "abc"))print(IsExist(root, "abcd"))
这篇关于CareerCup Trie Prefix Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
