### 主要收获二 — Prefix Tree

words: "aaa","aab","abc"
a
/ \
a   b
/ \   \
a   b   c


### 题目

Implement a trie with insert, search, and startsWith methods.

Note: You may assume that all inputs are consist of lowercase letters a-z.

### 基本思路

• insert(): $O(1)$
• search(): $O(1)$
• startsWith(): $O(n)$

• insert(): $O(n)$
• search(): $O(\log_{}{n})$
• startsWith(): $O(\log_{}{n})$

• insert(): $O(\log_{}{n})$
• search(): $O(\log_{}{n})$
• startsWith(): $O(\log_{}{n})$

### 解法一：基于二叉搜索树的Trie

public int compare(String s1, String s2) {
int n1 = s1.length();
int n2 = s2.length();
int min = Math.min(n1, n2);
for (int i = 0; i < min; i++) {
char c1 = s1.charAt(i);
char c2 = s2.charAt(i);
if (c1 != c2) {
c1 = Character.toUpperCase(c1);
c2 = Character.toUpperCase(c2);
if (c1 != c2) {
c1 = Character.toLowerCase(c1);
c2 = Character.toLowerCase(c2);
if (c1 != c2) {
// No overflow because of numeric promotion
return c1 - c2;
}
}
}
}
return n1 - n2;
}


1. 先比较共有长度部分。比如aabbaaa，共有长度为3。在共有长度内就分出了胜负。
aabb
aaa
|
共有长度 = 3

2. 如果，共有长度内分不出胜负，那就是更长的那个字符串更大。比如aaabbbaaa，共有长度3之内，没有分出大小，所以较长的aaabbb更大。
aaabbb
aaa
|
共有长度 = 3


• begin = aaa
• end = aab

#### 代码

public class Trie {
private static class TreeNode {
private String val;
private TreeNode left;
private TreeNode right;
private TreeNode(String s) {
val = s;
}
}
private TreeNode dummy;
/** Initialize your data structure here. */
public Trie() {
dummy = new TreeNode("");
}

/** Inserts a word into the trie. */
public void insert(String word) {
TreeNode pre = dummy, cur = dummy.right;
boolean goLeft = false;
while (cur != null) {
int diff = word.compareTo(cur.val);
pre = cur;
if (diff < 0) { // go left
cur = cur.left;
goLeft = true;
} else if (diff > 0) { // go right
cur = cur.right;
goLeft = false;
} else { // word == cur.val (word already exist)
return;
}
}
TreeNode newNode = new TreeNode(word);
if (goLeft) {
pre.left = newNode;
} else {
pre.right = newNode;
}
}

/** Returns if the word is in the trie. */
public boolean search(String word) {
TreeNode cur = dummy.right;
while (cur != null) {
int diff = cur.val.compareTo(word);
if (diff < 0) { // go right
cur = cur.right;
} else if (diff > 0) { // go left
cur = cur.left;
} else { // found target
return true;
}
}
return false;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
String begin = firstLargerEqual(prefix);
String nextPrefix = nextString(prefix);
String end = firstLargerEqual(nextPrefix);
return ((begin == null && end == null) || begin.equals(end))? false : true;
}

/** The last character add one */
private String nextString(String word) {
char[] letters = word.toCharArray();
int tail = letters.length;
if (tail == 0) { return "a"; }
for (int i = letters.length-1; i >= 0; i--) {
if (letters[i] < 'z') {
letters[i] = (char)(letters[i] + 1);
break;
} else {
tail--;
}
}
return (tail == 0)? "{" : new String(Arrays.copyOfRange(letters,0,tail));   // "{"是z之后的第一个字符
}

/** Returns the first element that >= the given String
*/
private String firstLargerEqual(String word) {
String lastLarger = null;
TreeNode pre = dummy, cur = dummy.right;
while (cur != null) {
int diff = cur.val.compareTo(word);
if (diff > 0) { // go left
lastLarger = cur.val;
cur = cur.left;
} else if (diff < 0) { // go right
cur = cur.right;
} else { // found word
return word;
}
}
return lastLarger;
}
}


### 解法二：基于Prefix Tree

words: "aaa","aab","abc"
a
/ \
a   b
/ \   \
a   b   c


• insert(): $O(\log_{}{n})$
• search(): $O(\log_{}{n})$
• startsWith(): $O(\log_{}{n})$

#### 代码

public class Trie {
private static class TreeNode {
private char val;
private boolean isWord;
private TreeNode[] children = new TreeNode[26];
private TreeNode(char c) {
val = c;
}
}
private TreeNode root = new TreeNode('\u0000');
/** Initialize your data structure here. */
public Trie() { }

/** Inserts a word into the trie. */
public void insert(String word) {
TreeNode cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
int offset = c - 'a';
TreeNode node = cur.children[offset];
if (node == null) {
node = new TreeNode(c);
cur.children[offset] = node;
}
cur = node;
}
cur.isWord = true;
}

/** Returns if the word is in the trie. */
public boolean search(String word) {
TreeNode cur = root;
for (int i = 0; i < word.length(); i++) {
int offset = word.charAt(i) - 'a';
if (cur.children[offset] == null) {
return false;
} else {
cur = cur.children[offset];
}
}
return cur.isWord;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TreeNode cur = root;
for (int i = 0; i < prefix.length(); i++) {
int offset = prefix.charAt(i) - 'a';
if (cur.children[offset] == null) {
return false;
} else {
cur = cur.children[offset];
}
}
return true;
}

}