208. Implement Trie (Prefix Tree)
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.
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 temp= root;
for(char c: word.toCharArray()){
int i=c-'a';
if(temp.children[i]==null)
{
TrieNode newNode=new TrieNode();
temp.children[i]=newNode;
}
temp=temp.children[i];
}
temp.end=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode temp= root;
for(char c: word.toCharArray()){
int i=c-'a';
if(temp.children[i]==null){
return false;
}
temp=temp.children[i];
}
return temp.end;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode temp= root;
for(char c: prefix.toCharArray()){
int i=c-'a';
if(temp.children[i]==null){
return false;
}
temp=temp.children[i];
}
return temp!=null;
}
static class TrieNode{
TrieNode[] children=new TrieNode[26];
boolean end=false;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/字典树主要有如下三点性质：
-
根节点不包含字符，除根节点意外每个节点只包含一个字符。
-
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
-
每个节点的所有子节点包含的字符串不相同。
字母树的插入（Insert）、删除（ Delete）和查找（Find）都非常简单，用一个一重循环即可，即第i 次循环找到前i 个字母所对应的子树，然后进行相应的操作。实现这棵字母树，我们用最常见的数组保存（静态开辟内存）即可，当然也可以开动态的指针类型（动态开辟内存）。至于结点对儿子的指向，一般有三种方法：
1、对每个结点开一个字母集大小的数组，对应的下标是儿子所表示的字母，内容则是这个儿子对应在大数组上的位置，即标号；
2、对每个结点挂一个链表，按一定顺序记录每个儿子是谁；
3、使用左儿子右兄弟表示法记录这棵树。
三种方法，各有特点。第一种易实现，但实际的空间要求较大；第二种，较易实现，空间要求相对较小，但比较费时；第三种，空间要求最小，但相对费时且不易写。
我们这里只来实现第一种方法，这种方法实现起来简单直观，字母的字典树每个节点要定义一个大小为 26 的子节点指针数组，然后用一个标志符用来记录到当前位置为止是否为一个词，初始化的时候讲 26 个子节点都赋为空。那么 insert 操作只需要对于要插入的字符串的每一个字符算出其的位置，然后找是否存在这个子节点，若不存在则新建一个，然后再查找下一个。查找词和找前缀操作跟 insert 操作都很类似，不同点在于若不存在子节点，则返回 false。查找次最后还要看标识位，而找前缀直接返回 true 即可。代码如下：
public class Sort {
public static void main(String[] args) {
Sort sort = new Sort();
System.out.println("sort:");
int[] a = new int[]{1, 8, 2, 9, 6, 7, 5, 0, 4, 3};
sort.quickSort(a, 0, a.length-1);
System.out.println(Arrays.toString(a));
}
private void quickSort(int[] a, int start, int end){
if(start<end){
// 选取第一个节点为标示，第一次遍历让比pivot小的数字都移到左边，比pivot大的都移到右边
int pivot = a[start];
int i = start;
int j = end;
while(i<j){
// 从后往前看，如果i<j，并且a[j]比pivot大，那么j继续往前移动
while(i<j&&a[j]>pivot){
j--;
}
// 如果i<j，防止数组越界，同时也说明上述while循环结束的条件是a[j]<pivot
if(i<j){
// 此时将a[i]与a[j]交换一下，同时把pivot移动到右边，这时候pivot右侧的数字全部比pivot大
a[i] = a[j];
a[j] = pivot;
// a[i]是之前的a[j],已经在pivot左侧了，所以不用继续比较，往后移动一个i
i++;
}
// 从前往后看，如果i<j, 并且a[i]<pivot，那么i继续往右移动
while(i<j&&a[i]<pivot){
i++;
}
// 如果i<j，防止数组越界，同时也说明上述while循环结束的条件是a[i]>pivot
if(i<j){
// 此时将a[j]与a[i]交换一下，因此当前的a[j]比pivot大，同时把pivot移动到左边，这时候pivot左侧的数字全部比pivot小
a[j] =a[i];
a[i] = pivot;
// a[j]是之前的a[i],已经在pivot右侧了，而且刚才比较发现比pivot大，所以不用继续比较，往前移动一个j
j--;
}
}
// 最后跳出循环不在移动的时候，说明i=j移到了中间部分，且左侧的值都比pivot小，且右侧的值都比pivot大，此时再给a[i]赋值pivot，可省略这一步
a[i]= pivot;
// 递归执行，i左侧
quickSort(a, start, i-1);
// 递归执行，i右侧
quickSort(a,i+1,end);
}
}
}