1.1 什么是Trie树
Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
它有3个基本性质：
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符都不相同。
1.2 树的构建
举个在网上流传颇广的例子，如下：
题目：给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。
分析：这题当然可以用hash来解决，但是本文重点介绍的是trie树，因为在某些方面它的用途更大。比如说对于某一个单词，我们要询问它的前缀是否出现过。这样hash就不好搞了，而用trie还是很简单。
现在回到例子中，如果我们用最傻的方法，对于每一个单词，我们都要去查找它前面的单词中是否有它。那么这个算法的复杂度就是O(n^2)。显然对于100000的范围难以接受。现在我们换个思路想。假设我要查询的单词是abcd，那么在他前面的单词中，以b，c，d，f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的，在以a开头中的单词中，我们只要考虑以b作为第二个字母的，一次次缩小范围和提高针对性，这样一个树的模型就渐渐清晰了。
对于每一个节点，从根遍历到他的过程就是一个单词，如果这个节点被标记为红色，就表示这个单词存在，否则不存在。
那么，对于一个单词，我只要顺着他从根走到对应的节点，再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色，就相当于插入了这个单词。
这样一来我们查询和插入可以一起完成（重点体会这个查询和插入是如何一起完成的，稍后，下文具体解释），所用时间仅仅为单词长度，在这一个样例，便是10。
我们可以看到，trie树每一层的节点数是26^i级别的。所以为了节省空间。我们用动态链表，或者用数组来模拟动态。空间的花费，不会超过单词数×单词长度。
1.3 前缀查询
上文中提到”比如说对于某一个单词，我们要询问它的前缀是否出现过。这样hash就不好搞了，而用trie还是很简单“。下面，咱们来看看这个前缀查询问题：
已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法：
最容易想到的：即从字符串集中从头往后搜，看每个字符串是否为字符串集中某个字符串的前缀，复杂度为O(n^2)。
使用hash：我们用hash存下所有字符串的所有的前缀子串，建立存有子串hash的复杂度为O(nlen)，而查询的复杂度为O(n) O(1)= O(n)。
使用trie：因为当查询如字符串abc是否为某个字符串的前缀时，显然以b,c,d....等不是以a开头的字符串就不用查找了。所以建立trie的复杂度为O(nlen)，而建立+查询在trie中是可以同时执行的，建立的过程也就可以成为查询的过程，hash就不能实现这个功能。所以总的复杂度为O(nlen)，实际查询的复杂度也只是O(len)。（说白了，就是Trie树的平均高度h为len，所以Trie树的查询复杂度为O（h）=O（len）。好比一棵二叉平衡树的高度为logN，则其查询，插入的平均时间复杂度亦为O（logN））。
208. Implement Trie (Prefix Tree)
class TrieNode {
Character val;
HashMap<Character, TrieNode> map;
boolean isWord;
public TrieNode() {
val = null;
map = new HashMap<>();
isWord = false;
}
public TrieNode(char ch) {
val = ch;
map = new HashMap<>();
isWord = false;
}
}
public class Trie {
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode cur = root;
for (int i = 0; i < word.length(); ++i) {
char ch = word.charAt(i);
if (!cur.map.containsKey(ch)) {
TrieNode node = new TrieNode(ch);
cur.map.put(ch, node);
}
cur = cur.map.get(ch);
}
cur.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode cur = root;
for (int i = 0; i < word.length(); ++i) {
char ch = word.charAt(i);
if (!cur.map.containsKey(ch)) return false;
cur = cur.map.get(ch);
}
return cur.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode cur = root;
for (int i = 0; i < prefix.length(); ++i) {
char ch = prefix.charAt(i);
if (!cur.map.containsKey(ch)) return false;
cur = cur.map.get(ch);
}
return true;
}
}
211. Add and Search Word - Data structure design
其实这题如果没有 wildcard，直接用 hashmap 就撸完了。。。因为没有 “前缀查询” 这个可以明显区分 trie 和 hashmap 查询性能的操作。
题目设计者不会这么善罢甘休的，于是他们引入了 wildcard
class TrieNode {
Character val;
Map<Character, TrieNode> map;
boolean isWord;
public TrieNode() {
val = null;
map = new HashMap<>();
isWord = false;
}
public TrieNode(char ch) {
val = ch;
map = new HashMap<>();
isWord = false;
}
}
public class WordDictionary {
private TrieNode root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); ++i) {
char ch = word.charAt(i);
if (!node.map.containsKey(ch)) {
node.map.put(ch, new TrieNode(ch));
}
node = node.map.get(ch);
}
node.isWord = true;
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
public boolean search(String word) {
return search(word, 0, root);
}
private boolean search(String word, int index, TrieNode node) {
if (index == word.length()) return node.isWord;
char ch = word.charAt(index);
if (ch == '.') {
Set<Character> set = node.map.keySet();
for (Character next : set) {
if(search(word, index + 1, node.map.get(next))) return true;
}
return false;
} else {
if (!node.map.containsKey(ch)) return false;
else return search(word, index + 1, node.map.get(ch));
}
}
}
212. Word Search II
public class Solution {
private class TrieNode {
char ch;
TrieNode[] map;
boolean isWord;
public TrieNode() {
map = new TrieNode[26];
}
public TrieNode(char ch) {
this.ch = ch;
map = new TrieNode[26];
}
}
public List<String> findWords(char[][] board, String[] words) {
List<String> result = new ArrayList<>();
if (board == null || board.length == 0 ||
words == null || words.length == 0) return result;
TrieNode root = new TrieNode();
for (String word : words) {
add(word, root);
}
for (int i = 0; i < board.length; ++i) {
for (int j = 0; j < board[0].length; ++j) {
searchAdd(root, board, i, j, result, new StringBuilder());
}
}
return result;
}
private void add(String word, TrieNode root) {
TrieNode node = root;
for (int i = 0; i < word.length(); ++i) {
char ch = word.charAt(i);
int index = ch - 'a';
if (node.map[index] == null) {
node.map[index] = new TrieNode(ch);
}
node = node.map[index];
}
node.isWord = true;
}
private void searchAdd(TrieNode root, char[][] board, int row, int col,
List<String> result, StringBuilder sb) {
if (root.isWord) {
if (!result.contains(sb.toString())) result.add(sb.toString());
}
if (row < 0 || row >= board.length) return;
if (col < 0 || col >= board[0].length) return;
if (board[row][col] == '#') return;
char ch = board[row][col];
int index = ch - 'a';
if (root.map[index] == null) {
return;
} else {
int len = sb.length();
sb.append(ch);
board[row][col] = '#';
searchAdd(root.map[index], board, row + 1, col, result, sb);
searchAdd(root.map[index], board, row - 1, col, result, sb);
searchAdd(root.map[index], board, row, col + 1, result, sb);
searchAdd(root.map[index], board, row, col - 1, result, sb);
board[row][col] = ch;
sb.setLength(len);
}
}
}
Trie Serialization
class Solution {
public String serialize(TrieNode root) {
if (root == null)
return "";
StringBuffer sb = new StringBuffer();
sb.append("<");
Iterator iter = root.children.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry)iter.next();
Character key = (Character)entry.getKey();
TrieNode child = (TrieNode)entry.getValue();
sb.append(key);
sb.append(serialize(child));
}
sb.append(">");
return sb.toString();
}
public TrieNode deserialize(String data) {
// Write your code here
if (data == null || data.length() == 0)
return null;
TrieNode root = new TrieNode();
TrieNode current = root;
Stack<TrieNode> path = new Stack<TrieNode>();
for (Character c : data.toCharArray()) {
switch (c) {
case '<':
path.push(current);
break;
case '>':
path.pop();
break;
default:
current = new TrieNode();
path.peek().children.put(c, current);
}
}
return root;
}
}
425. Word Squares
暴力写DFS很简单，但是时间复杂度肯定爆炸。1000个单词，最长5，1000^5。
冗余一
- 第一个词填了wall 后，第二个词必须以a开头
- 第二个词填了area后，第三个词必须以le开头
冗余二
- 第一个词填了wall ，第二个词想填area的话
- 字典中必须有以le la开头的单词，否则没有的话就不能填area
其实这两个冗余是一个。
怎么实现?
用Hash or Trie树记录下以某个前缀开头的有哪些单词
比如以l 开头的有lead lady，以le开头的有lead， 以lea开头的有lead
每次只用从特定开头的单词中继续往后搜
怎么记录状态的?
- l 第几层，放在DFS的函数参数中
- wordLen 不改变的，放在全局变量中
- squares 放在全局变量中，并在DFS时滚动
- pre 前缀不好记录，在DFS过程中临时算的
public class Solution {
class TrieNode {
List<String> startWith;
TrieNode[] children;
TrieNode() {
startWith = new ArrayList<>();
children = new TrieNode[26];
}
}
class Trie {
TrieNode root;
Trie(String[] words) {
root = new TrieNode();
for (String w : words) {
TrieNode cur = root;
for (char ch : w.toCharArray()) {
int idx = ch - 'a';
if (cur.children[idx] == null)
cur.children[idx] = new TrieNode();
cur.children[idx].startWith.add(w);
cur = cur.children[idx];
}
}
}
List<String> findByPrefix(String prefix) {
List<String> ans = new ArrayList<>();
TrieNode cur = root;
for (char ch : prefix.toCharArray()) {
int idx = ch - 'a';
if (cur.children[idx] == null)
return ans;
cur = cur.children[idx];
}
ans.addAll(cur.startWith);
return ans;
}
}
public List<List<String>> wordSquares(String[] words) {
List<List<String>> ans = new ArrayList<>();
if (words == null || words.length == 0)
return ans;
int len = words[0].length();
Trie trie = new Trie(words);
List<String> ansBuilder = new ArrayList<>();
for (String w : words) {
ansBuilder.add(w);
search(len, trie, ans, ansBuilder);
ansBuilder.remove(ansBuilder.size() - 1);
}
return ans;
}
private void search(int len, Trie tr, List<List<String>> ans,
List<String> ansBuilder) {
if (ansBuilder.size() == len) {
ans.add(new ArrayList<>(ansBuilder));
return;
}
int idx = ansBuilder.size();
StringBuilder prefixBuilder = new StringBuilder();
for (String s : ansBuilder)
prefixBuilder.append(s.charAt(idx));
List<String> startWith = tr.findByPrefix(prefixBuilder.toString());
for (String sw : startWith) {
ansBuilder.add(sw);
search(len, tr, ans, ansBuilder);
ansBuilder.remove(ansBuilder.size() - 1);
}
}
}