算法（五） 前缀树

前缀树结构

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

前缀树的基本操作

插入字符串：从根节点开始，依次插入字符串的每个字符。如果路径不存在，则创建新节点。最后一个节点标记为字符串的结束。

删除字符串：从根节点开始，依次减少路径上节点的计数。如果某节点的计数为零，则删除该节点。

查询字符串出现次数：沿路径遍历字符串，若路径完整且结束节点存在，则返回字符串的计数。

查询前缀数量：沿路径遍历前缀，若路径完整，则返回最后节点的通过计数。

节点的结构

      class TrieNode {
	public int pass;
	public int end;
	public TrieNode[] nexts;

	public TrieNode() {
		pass = 0;
		end = 0;
		nexts = new TrieNode[26];
	}
}

插入字符串

      public void insert(String word) {
	TrieNode node = root;
	node.pass++;
	for (int i = 0, path; i < word.length(); i++) { // 从左往右遍历字符
		path = word.charAt(i) - 'a'; // 由字符，对应成走向哪条路
		if (node.nexts[path] == null) {
			node.nexts[path] = new TrieNode();
		}
		node = node.nexts[path];
		node.pass++;
	}
	node.end++;
}

查询字符串出现次数

  // 查询前缀树里，word单词出现了几次
public int countWordsEqualTo(String word) {
	TrieNode node = root;
	for (int i = 0, path; i < word.length(); i++) {
		path = word.charAt(i) - 'a';
		if (node.nexts[path] == null) {
			return 0;
		}
		node = node.nexts[path];
	}
	return node.end;
}

查询前缀数量

      // 查询前缀树里，有多少单词以pre做前缀
public int countWordsStartingWith(String pre) {
	TrieNode node = root;
	for (int i = 0, path; i < pre.length(); i++) {
		path = pre.charAt(i) - 'a';
		if (node.nexts[path] == null) {
			return 0;
		}
		node = node.nexts[path];
	}
	return node.pass;
}

删除字符串

  	// 如果之前word插入过前缀树，那么此时删掉一次
// 如果之前word没有插入过前缀树，那么什么也不做
public void erase(String word) {
	if (countWordsEqualTo(word) > 0) {
		TrieNode node = root;
		node.pass--;
		for (int i = 0, path; i < word.length(); i++) {
			path = word.charAt(i) - 'a';
			if (--node.nexts[path].pass == 0) {
				node.nexts[path] = null;
				return;
			}
			node = node.nexts[path];
		}
		node.end--;
	}
}

使用静态数组实现前缀树

   // 如果将来增加了数据量，就改大这个值
public static int MAXN = 150001;

public static int[][] tree = new int[MAXN][26];

public static int[] end = new int[MAXN];

public static int[] pass = new int[MAXN];

public static int cnt;

public static void build() {
	cnt = 1;
}

public static void insert(String word) {
	int cur = 1;
	pass[cur]++;
	for (int i = 0, path; i < word.length(); i++) {
		path = word.charAt(i) - 'a';
		if (tree[cur][path] == 0) {
			tree[cur][path] = ++cnt;
		}
		cur = tree[cur][path];
		pass[cur]++;
	}
	end[cur]++;
}

public static int search(String word) {
	int cur = 1;
	for (int i = 0, path; i < word.length(); i++) {
		path = word.charAt(i) - 'a';
		if (tree[cur][path] == 0) {
			return 0;
		}
		cur = tree[cur][path];
	}
	return end[cur];
}

public static int prefixNumber(String pre) {
	int cur = 1;
	for (int i = 0, path; i < pre.length(); i++) {
		path = pre.charAt(i) - 'a';
		if (tree[cur][path] == 0) {
			return 0;
		}
		cur = tree[cur][path];
	}
	return pass[cur];
}

public static void delete(String word) {
	if (search(word) > 0) {
		int cur = 1;
		// 下面这一行代码，讲课的时候没加
		// 本题不会用到pass[1]的信息，所以加不加都可以，不过正确的写法是加上
		pass[cur]--;
		for (int i = 0, path; i < word.length(); i++) {
			path = word.charAt(i) - 'a';
			if (--pass[tree[cur][path]] == 0) {
				tree[cur][path] = 0;
				return;
			}
			cur = tree[cur][path];
		}
		end[cur]--;
	}
}

public static void clear() {
	for (int i = 1; i <= cnt; i++) {
		Arrays.fill(tree[i], 0);
		end[i] = 0;
		pass[i] = 0;
	}
}

相关题目

查询数组中两个数的异或最大值

思路：我们使用每一个数，根据他的每一位去构建一个前缀树。然后依次遍历每一个数，从最高位开始遍历，我希望找到跟我不一样的位，于是我在前缀树里面查找。如果存在那么把这个位置变成1加入答案，如果不存在那么把这个位置变成0加入答案。然后跳到下一个节点树去。

   // 前缀树的做法
// 好想
public static int findMaximumXOR1(int[] nums) {
	build(nums);
	int ans = 0;
	for (int num : nums) {
		ans = Math.max(ans, maxXor(num));
	}
	clear();
	return ans;
}

// 准备这么多静态空间就够了，实验出来的
// 如果测试数据升级了规模，就改大这个值
public static int MAXN = 3000001;

public static int[][] tree = new int[MAXN][2];

// 前缀树目前使用了多少空间
public static int cnt;

// 数字只需要从哪一位开始考虑
public static int high;

public static void build(int[] nums) {
	cnt = 1;
	// 找个最大值
	int max = Integer.MIN_VALUE;
	for (int num : nums) {
		max = Math.max(num, max);
	}
	// 计算数组最大值的二进制状态，有多少个前缀的0
	// 可以忽略这些前置的0，从left位开始考虑
	high = 31 - Integer.numberOfLeadingZeros(max);
	for (int num : nums) {
		insert(num);
	}
}

public static void insert(int num) {
	int cur = 1;
	for (int i = high, path; i >= 0; i--) {
		path = (num >> i) & 1;
		if (tree[cur][path] == 0) {
			tree[cur][path] = ++cnt;
		}
		cur = tree[cur][path];
	}
}

public static int maxXor(int num) {
	// 最终异或的结果(尽量大)
	int ans = 0;
	// 前缀树目前来到的节点编号
	int cur = 1;
	for (int i = high, status, want; i >= 0; i--) {
		// status : num第i位的状态
		status = (num >> i) & 1;
		// want : num第i位希望遇到的状态
		want = status ^ 1;
		if (tree[cur][want] == 0) { // 询问前缀树，能不能达成
			// 不能达成
			want ^= 1;
		}
		// want变成真的往下走的路
		ans |= (status ^ want) << i;
		cur = tree[cur][want];
	}
	return ans;
}

public static void clear() {
	for (int i = 1; i <= cnt; i++) {
		tree[i][0] = tree[i][1] = 0;
	}
}

在二维网格中，搜索单词组返回能找到的单词组

思路：回溯+前缀树减枝

关键点：1.把走过的格子，标为0，这样不会重复走，但是需要恢复现场

2.利用前缀树减枝，首先利用单词组构建出前缀树。每次递归的时候根据前缀树有没有路径来判断这个格子里面的单词能不能要。除了路径还要判断这条路径下还有没有剩余的未探索单词（利用pass数组）。

3.巧用pass跟end数组。pass[i] 表示当前节点剩余还未收集的单词，end[i] 表示在当前节点完结的单词，可以直接加入ans。

public static List<String> findWords(char[][] board, String[] words) {
	build(words);
	List<String> ans = new ArrayList<>();
	for (int i = 0; i < board.length; i++) {
		for (int j = 0; j < board[0].length; j++) {
			dfs(board, i, j, 1, ans);
		}
	}
	clear();
	return ans;
}

// board : 二维网格
// i,j : 此时来到的格子位置，i行、j列
// t : 前缀树的编号
// List<String> ans : 收集到了哪些字符串，都放入ans
// 返回值 : 收集到了几个字符串
public static int dfs(char[][] board, int i, int j, int t, List<String> ans) {
	// 越界 或者 走了回头路，直接返回0
	if (i < 0 || i == board.length || j < 0 || j == board[0].length || board[i][j] == 0) {
		return 0;
	}
	// 不越界 且 不是回头路
	// 用tmp记录当前字符
	char tmp = board[i][j];
	// 路的编号
	// a -> 0
	// b -> 1
	// ...
	// z -> 25
	int road = tmp - 'a';
	t = tree[t][road];
       // 不存在该路径，或者该路径下的单词已经被你找出来完了  其实应该写成 t==0 || pass[t]==0 但是初始化的时候pass就是从1开始，所以这里可以不用判断
	if (pass[t] == 0) {
		return 0;
	}
	// i，j位置有必要来
	// fix ：从当前i，j位置出发，一共收集到了几个字符串
	int fix = 0;
	if (end[t] != null) {
		fix++;
		ans.add(end[t]);
		end[t] = null;
	}
	// 把i，j位置的字符，改成0，后续的过程，是不可以再来到i，j位置的！
	board[i][j] = 0;
	fix += dfs(board, i - 1, j, t, ans);
	fix += dfs(board, i + 1, j, t, ans);
	fix += dfs(board, i, j - 1, t, ans);
	fix += dfs(board, i, j + 1, t, ans);
       // 减去已经找到的单词数量
	pass[t] -= fix;
       // 恢复现场
	board[i][j] = tmp;
	return fix;
}

public static int MAXN = 10001;

public static int[][] tree = new int[MAXN][26];

public static int[] pass = new int[MAXN];

public static String[] end = new String[MAXN];

public static int cnt;

public static void build(String[] words) {
	cnt = 1;
	for (String word : words) {
		int cur = 1;
		pass[cur]++;
		for (int i = 0, path; i < word.length(); i++) {
			path = word.charAt(i) - 'a';
			if (tree[cur][path] == 0) {
				tree[cur][path] = ++cnt;
			}
			cur = tree[cur][path];
			pass[cur]++;
		}
		end[cur] = word;
	}
}

public static void clear() {
	for (int i = 1; i <= cnt; i++) {
		Arrays.fill(tree[i], 0);
		pass[i] = 0;
		end[i] = null;
	}
}