Implement Trie (Prefix Tree) (M)
題目
Implement a trie with insert, search, and startsWith methods.
Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
Note:
- You may assume that all inputs are consist of lowercase letters
a-z. - All inputs are guaranteed to be non-empty strings.
題意
實作字典樹，
思路
每個結點最多可以有26個子結點，同時給每個結點設定一個標志位用來指明當前結點是否為一個單詞的結尾，
代碼實作
Java
class Trie {
private Node root;
/** Initialize your data structure here. */
public Trie() {
root = new Node();
}
/** Inserts a word into the trie. */
public void insert(String word) {
Node p = root;
for (char c : word.toCharArray()) {
if (p.children[c - 'a'] == null) {
p.children[c - 'a'] = new Node();
}
p = p.children[c - 'a'];
}
p.end = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Node p = prefix(word);
return p != null && p.end;
}
/**
* Returns if there is any word in the trie that starts with the given prefix.
*/
public boolean startsWith(String prefix) {
return prefix(prefix) != null;
}
private Node prefix(String word) {
Node p = root;
for (char c : word.toCharArray()) {
if (p.children[c - 'a'] == null) {
return null;
}
p = p.children[c - 'a'];
}
return p;
}
}
class Node {
Node[] children = new Node[26];
boolean end;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/6732.html
標籤：其他
上一篇：《劍指offer》2:青蛙跳臺階