前綴樹(shù)
在計(jì)算機(jī)科學(xué)中魄鸦，trie，又稱(chēng)前綴樹(shù)或字典樹(shù)啥纸，是一種有序樹(shù)号杏，用于保存關(guān)聯(lián)數(shù)組，其中的鍵通常是字符串斯棒。與二叉查找樹(shù)不同盾致，鍵不是直接保存在節(jié)點(diǎn)中，而是由節(jié)點(diǎn)在樹(shù)中的位置決定荣暮。一個(gè)節(jié)點(diǎn)的所有子孫都有相同的前綴庭惜，也就是這個(gè)節(jié)點(diǎn)對(duì)應(yīng)的字符串，而根節(jié)點(diǎn)對(duì)應(yīng)空字符串穗酥。一般情況下护赊，不是所有的節(jié)點(diǎn)都有對(duì)應(yīng)的值惠遏，只有葉子節(jié)點(diǎn)和部分內(nèi)部節(jié)點(diǎn)所對(duì)應(yīng)的鍵才有相關(guān)的值。
前綴樹(shù)
特點(diǎn)
前綴樹(shù)的查找效率高于哈希數(shù)組骏啰，但是空間消耗要大于哈希數(shù)組
實(shí)現(xiàn)
class Trie {
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode node = root;
for(char c : word.toCharArray()){
if(node.node[c-'a']==null){
node.node[c-'a'] = new TrieNode();
}
node = node.node[c-'a'];
}
node.item = word;//保存當(dāng)前葉子結(jié)點(diǎn)對(duì)應(yīng)的字符串
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node = root;
for(char c:word.toCharArray()){
if(node.node[c-'a']!=null)
node = node.node[c-'a'];
else
return false;
}
return word.equals(node.item);
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node = root;
for(char c : prefix.toCharArray()){
if(node.node[c-'a']!=null)
node = node.node[c-'a'];
else
return false;
}
return true;
}
}
class TrieNode{
TrieNode []node;
String item;
public TrieNode(){
node = new TrieNode[26];
item = "";
}
}
總結(jié)
前綴樹(shù)是字符串筆試中經(jīng)常會(huì)使用到的存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)节吮，要熟練前綴樹(shù)的創(chuàng)建與使用。
