https://www.jiuzhang.com/solution/implement-trie/
算法：字典树
思路：
- 题目要求实现一个Trie，包含插入、查找和查找前缀三个方法。
- Trie树也称字典树，因为其效率很高，所以在在字符串查找、前缀匹配等中应用很广泛，其高效率是以空间为代价的。
- 原理：利用串构建一个字典树，这个字典树保存了串的公共前缀信息，因此可以降低查询操作的复杂度。
- 定义结点Node里包含一个isWord(表示这个结点是否是一个单词的结尾)和一个大小为26的next。
1.定义一个根结点root作为整棵树的查找起点。
2.比如插入一个单词apple：
我们从root开始，依次往下查找a,p,p,l,e：如果在结点n的下一个字母里没有找到我们想要的字母ch，我们就增加新结点到结点n的next[]，式子next[ch-'a']=new Node()。
3.查找一个单词app：
我们从root开始，依次往下查找a,p,p：如果在结点n的下一个字母里没有找到我们想要的字母ch，那么说明不存在，返回False;如果有，那么继续往下找，直到查找的单词app找到最后一位，这时候我们判断一下这个位置的isWord是否为True，如果为True说明这是一个完整单词，否则只是部分，返回False。
4.查找一个前缀
查找一个前缀和查找一个单词的区别就是，当我们想要查找的前缀找到最后一位，不需要判断是否是完整的单词，直接返回True即可。如果不能全部找到则返回False。
复杂度
- 空间复杂度:字典树每个节点都需要用一个大小为26的数组来存储子节点的指针，所以空间复杂度较高。
- 时间复杂度：假设所有插入字符串长度之和为n，构建字典树的时间复杂度为O(n)；假设要查找的所有字符串长度之和为k，查找的时间复杂度为O(k)。因此时间复杂度为O(n+k)
public class Trie {
private class Node{
// isWord表示这个结点是否为一个单词的结尾
// next[]表示这个结点的下一个26个字母结点
public boolean isWord;
public Node[] next;
public Node() {
this.isWord = false;
this.next = new Node[26];
}
}
private Node root;
public Trie() {
root = new Node();
} /*
* @param word: a word
* @return: nothing
*/
public void insert(String word) {
Node now = root;
int n = word.length();
for (int i = 0; i < n; i++) {
// 依次寻找每个字符
// 如果所有下一个结点中没有当前字符，则增加新结点到下一个next[pos]
int pos = word.charAt(i) - 'a';
if (now.next[pos] == null) {
now.next[pos] = new Node();
}
now = now.next[pos];
}
now.isWord = true;
} /*
* @param word: A string
* @return: if the word is in the trie.
*/
public boolean search(String word) {// 查找单词
int n = word.length();
Node now = root;
for (int i = 0; i < n; i++) {
int ch = word.charAt(i) - 'a';
// 如果有下一个对应字符的结点，那么继续查找下一个结点
// 如果没有下一个对应字符的结点，那么说明查找单词失败
if (now.next[ch] != null) {
now = now.next[ch];
}
else {
return false;
}
}
// 如果每个字符都有且是完整单词，才说明查找单词成功
return now.isWord;
} /*
* @param prefix: A string
* @return: if there is any word in the trie that starts with the given prefix.
*/
public boolean startsWith(String prefix) {// 查找前缀
int n = prefix.length();
Node now = root;
for (int i = 0; i < n; i++) {
int ch = prefix.charAt(i) - 'a';
// 如果有下一个对应字符的结点，那么继续查找下一个结点
// 如果没有下一个对应字符的结点，那么说明查找前缀失败
if (now.next[ch] != null) {
now = now.next[ch];
}
else {
return false;
}
}
return true;
}
}
赞同
2
令狐冲精选
更新于 6/9/2021, 6:57:33 PM
Trie(前缀树) 的模板应用.
维基百科: https://zh.wikipedia.org/zh-hans/Trie
class TrieNode {
public:// Initialize your data structure here.TrieNode() {for (int i = 0; i < 26; i++)next[i] = NULL;isString = false;}TrieNode *next[26];bool isString;
};class Trie {
public:Trie() {root = new TrieNode();}// Inserts a word into the trie.void insert(string word) {TrieNode *p = root;for (int i = 0; i < word.size(); i++) {if (p->next[word[i]-'a'] == NULL) {p->next[word[i]-'a'] = new TrieNode();}p = p->next[word[i]-'a'];}p->isString = true;}// Returns if the word is in the trie.bool search(string word) {TrieNode *p = root;for (int i = 0; i < word.size(); i++) {if (p == NULL) return false;p = p->next[word[i]-'a'];}if (p == NULL || p->isString == false) return false;return true;}// Returns if there is any word in the trie// that starts with the given prefix.bool startsWith(string prefix) {TrieNode *p = root;for (int i = 0; i < prefix.size(); i++) {p = p->next[prefix[i]-'a'];if (p == NULL) return false;}return true;}private:TrieNode* root;
};赞同
1
令狐冲精选
更新于 6/9/2020, 4:03:58 AM
Trie(前缀树) 的模板应用.
维基百科: https://zh.wikipedia.org/zh-hans/Trie
// Version 1: Array of TrieNode
class TrieNode {private TrieNode[] children;public boolean hasWord;public TrieNode() {children = new TrieNode[26];hasWord = false;}public void insert(String word, int index) {if (index == word.length()) {this.hasWord = true;return;}int pos = word.charAt(index) - 'a';if (children[pos] == null) {children[pos] = new TrieNode();}children[pos].insert(word, index + 1);}public TrieNode find(String word, int index) {if (index == word.length()) {return this;}int pos = word.charAt(index) - 'a';if (children[pos] == null) {return null;}return children[pos].find(word, index + 1);}
}public class Trie {private TrieNode root;public Trie() {root = new TrieNode();}// Inserts a word into the trie.public void insert(String word) {root.insert(word, 0);}// Returns if the word is in the trie.public boolean search(String word) {TrieNode node = root.find(word, 0);return (node != null && node.hasWord);}// Returns if there is any word in the trie// that starts with the given prefix.public boolean startsWith(String prefix) {TrieNode node = root.find(prefix, 0);return node != null;}
}// Version 2: HashMap Version, this version will be TLE when you submit on LintCode
class TrieNode {// Initialize your data structure here.char c;HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();boolean hasWord;public TrieNode(){}public TrieNode(char c){this.c = c;}
}public class Trie {private TrieNode root;public Trie() {root = new TrieNode();}// Inserts a word into the trie.public void insert(String word) {TrieNode cur = root;HashMap<Character, TrieNode> curChildren = root.children;char[] wordArray = word.toCharArray();for(int i = 0; i < wordArray.length; i++){char wc = wordArray[i];if(curChildren.containsKey(wc)){cur = curChildren.get(wc);} else {TrieNode newNode = new TrieNode(wc);curChildren.put(wc, newNode);cur = newNode;}curChildren = cur.children;if(i == wordArray.length - 1){cur.hasWord= true;}}}// Returns if the word is in the trie.public boolean search(String word) {if(searchWordNodePos(word) == null){return false;} else if(searchWordNodePos(word).hasWord) return true;else return false;}// Returns if there is any word in the trie// that starts with the given prefix.public boolean startsWith(String prefix) {if(searchWordNodePos(prefix) == null){return false;} else return true;}public TrieNode searchWordNodePos(String s){HashMap<Character, TrieNode> children = root.children;TrieNode cur = null;char[] sArray = s.toCharArray();for(int i = 0; i < sArray.length; i++){char c = sArray[i];if(children.containsKey(c)){cur = children.get(c);children = cur.children;} else{return null;}}return cur;}
}赞同
1
令狐冲精选
更新于 6/9/2020, 4:03:58 AM
代码兼容Python 2 & 3 新建一个 TrieNode 的 class 用于表示 Trie 中的节点，包含 children 和 is_word 两个属性
Trie(前缀树) 的模板应用.
维基百科: https://zh.wikipedia.org/zh-hans/Trie
class TrieNode:def __init__(self):self.children = {}self.is_word = Falseclass Trie:def __init__(self):self.root = TrieNode()"""@param: word: a word@return: nothing"""def insert(self, word):node = self.rootfor c in word:if c not in node.children:node.children[c] = TrieNode()node = node.children[c]node.is_word = True"""return the node in the trie if exists """def find(self, word):node = self.rootfor c in word:node = node.children.get(c)if node is None:return Nonereturn node"""@param: word: A string@return: if the word is in the trie."""def search(self, word):node = self.find(word)return node is not None and node.is_word"""@param: prefix: A string@return: if there is any word in the trie that starts with the given prefix."""def startsWith(self, prefix):return self.find(prefix) is not None赞同
1
