題目
實現(xiàn)Trie Tree(前綴樹)包含 insert, search, 和 startsWith 這三個操作。
LeetCode.208
解析與編碼實現(xiàn)
- 什么是Trie Tree?
前綴樹皆怕，也稱為字典樹或查找樹，是一種樹形結(jié)構(gòu)翩剪。典型應(yīng)用是用于統(tǒng)計寿羞，排序和保存大量的字符串毯焕，利用字符串的公共前綴來減少查詢時間嘹狞，減少存儲空間岂膳，并且最大限度地減少無謂的字符串比較。
Trie Tree如圖所示——圖片來源于網(wǎng)絡(luò)
- Trie Tree Node的結(jié)構(gòu)定義
題目中要求磅网，輸入都是由小寫字母a-z構(gòu)成的谈截，一個Node初始化26個孩子節(jié)點(diǎn)引用（26個小寫英文字母），26個孩子節(jié)點(diǎn)使用數(shù)組結(jié)構(gòu)實現(xiàn)涧偷，a-z固定在對應(yīng)的數(shù)組元素上簸喂，雖然這樣會有存儲上的損耗，某些字母并沒有存在燎潮，但是通過a-z可以直接定位到數(shù)組的元素查詢時間復(fù)雜度O(1)喻鳄。
- insert操作可以沿著根節(jié)點(diǎn)root（不存儲任何值）依次向下遍歷和插入。
- startsWith操作前綴匹配确封，從root出發(fā)向下遍歷除呵，如果對應(yīng)的字符節(jié)點(diǎn)均存在，則返回true爪喘，表明找到了颜曾。只要一個字符對應(yīng)的節(jié)點(diǎn)不存在就沒有找到。
- search操作從root出發(fā)秉剑，需要全部匹配的同時泛豪，還要確定最后一個匹配的字符節(jié)點(diǎn)是否是存儲的字符串中的某個字符串最后的一個字符，也就是某個字符串的結(jié)束位置侦鹏。例如诡曙，樹中存儲了abcd，那么search(abc)時略水，匹配的最后一個字符節(jié)點(diǎn)是c价卤，而c不是存儲的字符串中的某個字符串最后的一個字符，所以不匹配聚请。這樣在Node結(jié)構(gòu)中我們需要增加一個標(biāo)志符用于標(biāo)記當(dāng)前節(jié)點(diǎn)是否是存儲的某個字符串的最后一個字符荠雕。
Trie Tree Node的結(jié)構(gòu)代碼如下：
class TrieNode {
private final int R = 26;
//代表的字符a-z
private String val;
//初始化26個子節(jié)點(diǎn)
private TrieNode[] children;
//標(biāo)記當(dāng)前節(jié)點(diǎn)是否是存儲的某個字符串的最后一個字符
private boolean isEnd;
public TrieNode(String val){
this.val = val;
this.children = new TrieNode[R];
this.isEnd = false;
}
public String getVal(){
return val;
}
public TrieNode[] getChildren(){
return children;
}
public void setIsEnd(boolean isEnd){
this.isEnd = isEnd;
}
public boolean getIsEnd(){
return this.isEnd;
}
}
- insert操作
沿著根節(jié)點(diǎn)root（不存儲任何值）依次向下遍歷，如果字符存在繼續(xù)向下驶赏，若不存在插入這個字符炸卑。當(dāng)?shù)竭_(dá)字符串的最后一個字符時，將節(jié)點(diǎn)的isEnd標(biāo)記為true煤傍，表示到這個字符為止存儲了一個字符串盖文。
代碼如下：
public void insert(String word) {
TrieNode parent = root;
//向下遍歷
for(int i = 0; i < word.length(); i++){
//a-z對應(yīng)的節(jié)點(diǎn)位置
int index = (int)(word.charAt(i) - 'a');
TrieNode child = parent.getChildren()[index];
//若不存在當(dāng)前字符的節(jié)點(diǎn)，插入
if (null == child){
child = new TrieNode(word.substring(i, i + 1));
parent.getChildren()[index] = child;
}
//繼續(xù)向下
parent = child;
}
//最后一個字符的節(jié)點(diǎn)isEnd標(biāo)記為true
parent.setIsEnd(true);
}
- search操作
從root出發(fā)蚯姆，向下遍歷尋找五续，如果字符節(jié)點(diǎn)不存在洒敏，則返回false。當(dāng)字符串都遍歷完成疙驾，并且對應(yīng)節(jié)點(diǎn)都存在時凶伙，需要判斷最后一個字符節(jié)點(diǎn)的isEnd是否為true，若為true則證明搜尋到對應(yīng)的字符串它碎。
代碼如下：
public boolean search(String word) {
TrieNode parent = root;
//從root出發(fā)函荣，向下遍歷尋找
for(int i = 0; i < word.length(); i++){
int index = (int)(word.charAt(i) - 'a');
TrieNode child = parent.getChildren()[index];
//如果字符節(jié)點(diǎn)不存在，則返回false
if (null == child){
return false;
}
parent = child;
}
//判斷最后一個字符節(jié)點(diǎn)的isEnd如果是false扳肛，表明不是字符串最后一個字符
if (!parent.getIsEnd()){
return false;
}
return true;
}
- startsWith操作
root出發(fā)向下遍歷傻挂，如果對應(yīng)的字符節(jié)點(diǎn)均存在，則返回true挖息。只要一個字符對應(yīng)的節(jié)點(diǎn)不存在就沒有找到金拒。
代碼如下：
public boolean startsWith(String prefix) {
TrieNode parent = root;
//從root出發(fā)，向下遍歷尋找
for(int i = 0; i < prefix.length(); i++){
int index = (int)(prefix.charAt(i) - 'a');
TrieNode child = parent.getChildren()[index];
//只要一個字符對應(yīng)的節(jié)點(diǎn)不存在就沒有找到
if (null == child){
return false;
}
parent = child;
}
return true;
}
完整代碼如下
class Trie {
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode(null);
}
public void insert(String word) {
TrieNode parent = root;
//向下遍歷
for(int i = 0; i < word.length(); i++){
//a-z對應(yīng)的節(jié)點(diǎn)位置
int index = (int)(word.charAt(i) - 'a');
TrieNode child = parent.getChildren()[index];
//若不存在當(dāng)前字符的節(jié)點(diǎn)套腹，插入
if (null == child){
child = new TrieNode(word.substring(i, i + 1));
parent.getChildren()[index] = child;
}
//繼續(xù)向下
parent = child;
}
//最后一個字符的節(jié)點(diǎn)isEnd標(biāo)記為true
parent.setIsEnd(true);
}
public boolean search(String word) {
TrieNode parent = root;
//從root出發(fā)绪抛，向下遍歷尋找
for(int i = 0; i < word.length(); i++){
int index = (int)(word.charAt(i) - 'a');
TrieNode child = parent.getChildren()[index];
//如果字符節(jié)點(diǎn)不存在，則返回false
if (null == child){
return false;
}
parent = child;
}
//判斷最后一個字符節(jié)點(diǎn)的isEnd如果是false沉迹，表明不是字符串最后一個字符
if (!parent.getIsEnd()){
return false;
}
return true;
}
public boolean startsWith(String prefix) {
TrieNode parent = root;
//從root出發(fā)睦疫，向下遍歷尋找
for(int i = 0; i < prefix.length(); i++){
int index = (int)(prefix.charAt(i) - 'a');
TrieNode child = parent.getChildren()[index];
//只要一個字符對應(yīng)的節(jié)點(diǎn)不存在就沒有找到
if (null == child){
return false;
}
parent = child;
}
return true;
}
}
class TrieNode {
private final int R = 26;
//代表的字符a-z
private String val;
//初始化26個子節(jié)點(diǎn)
private TrieNode[] children;
//標(biāo)記當(dāng)前節(jié)點(diǎn)是否是存儲的某個字符串的最后一個字符
private boolean isEnd;
public TrieNode(String val){
this.val = val;
this.children = new TrieNode[R];
this.isEnd = false;
}
public String getVal(){
return val;
}
public TrieNode[] getChildren(){
return children;
}
public void setIsEnd(boolean isEnd){
this.isEnd = isEnd;
}
public boolean getIsEnd(){
return this.isEnd;
}
}
