027.前缀树的相关题目

前置知识：静态空间方式实现前缀树、异或运算、递归

题目1.接头密匙 §

测试链接 §

接头密匙

答案 §

package main
 
import (
	"strconv"
	"strings"
)
 
const (
	MAXN = 2000001
	ROAD_COUNT = 12 // 0-9 # -
)
 
var (
	tree = [MAXN][ROAD_COUNT]int{}
	pass = [MAXN]int{}
	end  = [MAXN]int{}
	cnt  = 1
)
 
/**
 * @param b int整型二维数组
 * @param a int整型二维数组
 * @return int整型一维数组
 */
func countConsistentKeys(b [][]int, a [][]int) []int {
	ans := make([]int, len(b))
	for _, arr := range a {
		Insert(calcStr(arr))
	}
	for i, arr := range b {
		ans[i] = PrefixNumber(calcStr(arr))
	}
	Clear()
	return ans
}
 
func calcStr(arr []int) string {
	var builder strings.Builder
	n := len(arr)
	for i := 1; i < n; i++ {
		builder.WriteString(strconv.Itoa(arr[i] - arr[i-1]))
		builder.WriteByte('#')
	}
	return builder.String()
}
 
func Insert(word string) {
	n := len(word)
	treeIdx := 0
	pass[treeIdx]++
	for i := 0; i < n; i++ {
		idx := getIdx(word[i])
		if tree[treeIdx][idx] == 0 {
			tree[treeIdx][idx] = cnt
			cnt++
		}
		treeIdx = tree[treeIdx][idx]
		pass[treeIdx]++
	}
	end[treeIdx]++
}
 
func Search(word string) int {
	n := len(word)
	treeIdx := 0
	for i := 0; i < n; i++ {
		treeIdx = tree[treeIdx][getIdx(word[i])]
		if treeIdx == 0 {
			return 0
		}
		
	}
	return end[treeIdx]
}
 
func PrefixNumber(word string) int {
	n := len(word)
	treeIdx := 0
	for i := 0; i < n; i++ {
		treeIdx = tree[treeIdx][getIdx(word[i])]
		if treeIdx == 0 {
			return 0
		}
		
	}
	return pass[treeIdx]
}
 
func Delete(word string) {
	if Search(word) == 0 {
		return
	}
	n := len(word)
	treeIdx := 0
	pass[treeIdx]--
	for i := 0; i < n; i++ {
		idx := getIdx(word[i])
		pass[tree[treeIdx][idx]]--
		if pass[tree[treeIdx][idx]] == 0 {
			tree[treeIdx][idx] = 0
			return
		}
		treeIdx = tree[treeIdx][idx]
	}
	end[treeIdx]--
}
 
func Clear() {
	for i := 0; i < cnt; i++ {
		for j := 0; j < ROAD_COUNT; j++ {
			tree[i][j] = 0
		}
		pass[i] = 0
		end[i] = 0
	}
	cnt = 1
}
 
func getIdx(char byte) int {
	if char == '-' {
		return 10
	}
	if char == '#' {
		return 11
	}
	return int(char - '0')
}

复杂度 §

• 时间复杂度：$O(a数组的数字个数\ast 10)+O(b数组的数字个数\ast 10)$
• 空间复杂度：$O(a数组的数字个数\ast 10)$，这是树上的节点数量

其中，10 是指 int32 差值的十进制字符长度，这只是大体估计，没有算上 - 和 #

题目 2.数组中两个数的最大异或值 §

题目描述 §

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n

测试链接 §

421.数组中两个数的最大异或值

思路 §

以数字的二进制字符串构建前缀树

答案 §

const (
	INT_BIT_COUNT = int(unsafe.Sizeof(int(0)) * 8) // int 占的位数
	MAXN          = 3000001
	ROAD_COUNT    = 2 // 0 1
)
 
var (
	tree = [MAXN][ROAD_COUNT]int{}
	pass = [MAXN]int{}
	end  = [MAXN]int{}
	cnt  = 1
 
	high int // 最高哪个位有 1
)
 
func findMaximumXOR(nums []int) int {
	ans := 0 // 自己可以异或自己，所以至少可以是 0
	calcHigh(nums)
	for _, num := range nums {
		Insert(getBinaryStr(num))
	}
	for _, num := range nums {
		prefix := make([]byte, high)
		curAns := 0
		for i := high - 1; i >= 0; i-- {
			// 想要的
			prefix[high-1-i] = '0'
			if num>>i&1 == 0 {
				prefix[high-1-i] = '1'
			}
			if PrefixNumber(string(prefix[:high-i])) > 0 {
				curAns |= 1 << i
			} else {
				// 没有：只能接受拥有的
				if prefix[high-1-i] == '0' {
					prefix[high-1-i] = '1'
				} else {
					prefix[high-1-i] = '0'
				}
			}
		}
		if curAns > ans {
			ans = curAns
		}
	}
	Clear()
	return ans
}
 
// 计算最高哪个位有 1
func calcHigh(nums []int) {
	maxx := 0
	for _, num := range nums {
		if num > maxx {
			maxx = num
		}
	}
	high = INT_BIT_COUNT - bits.LeadingZeros(uint(maxx))
}
 
func getBinaryStr(num int) string {
	ans := make([]byte, high)
	for i := high - 1; i >= 0; i-- {
		ans[high-1-i] = byte(num>>i&1) + '0'
	}
	return string(ans)
}
 
func Insert(word string) {
	n := len(word)
	treeIdx := 0
	pass[treeIdx]++
	for i := 0; i < n; i++ {
		idx := getIdx(word[i])
		if tree[treeIdx][idx] == 0 {
			tree[treeIdx][idx] = cnt
			cnt++
		}
		treeIdx = tree[treeIdx][idx]
		pass[treeIdx]++
	}
	end[treeIdx]++
}
 
func Search(word string) int {
	n := len(word)
	treeIdx := 0
	for i := 0; i < n; i++ {
		treeIdx = tree[treeIdx][getIdx(word[i])]
		if treeIdx == 0 {
			return 0
		}
 
	}
	return end[treeIdx]
}
 
func PrefixNumber(word string) int {
	n := len(word)
	treeIdx := 0
	for i := 0; i < n; i++ {
		treeIdx = tree[treeIdx][getIdx(word[i])]
		if treeIdx == 0 {
			return 0
		}
 
	}
	return pass[treeIdx]
}
 
func Delete(word string) {
	if Search(word) == 0 {
		return
	}
	n := len(word)
	treeIdx := 0
	pass[treeIdx]--
	for i := 0; i < n; i++ {
		idx := getIdx(word[i])
		pass[tree[treeIdx][idx]]--
		if pass[tree[treeIdx][idx]] == 0 {
			tree[treeIdx][idx] = 0
			return
		}
		treeIdx = tree[treeIdx][idx]
	}
	end[treeIdx]--
}
 
func Clear() {
	for i := 0; i < cnt; i++ {
		for j := 0; j < ROAD_COUNT; j++ {
			tree[i][j] = 0
		}
		pass[i] = 0
		end[i] = 0
	}
	cnt = 1
}
 
func getIdx(char byte) int {
	return int(char - '0')
}

优化：

const (
	INT_BIT_COUNT = int(unsafe.Sizeof(int(0)) * 8) // int 占的位数
	MAXN          = 3000001
	ROAD_COUNT    = 2 // 0 1
)
 
var (
	tree = [MAXN][ROAD_COUNT]int{}
	cnt  = 1
 
	high int // 最高哪个位有 1
)
 
func findMaximumXOR(nums []int) int {
	ans := 0 // 自己可以异或自己，所以至少可以是 0
	maxx := 0
	for _, num := range nums {
		if num > maxx {
			maxx = num
		}
	}
	high = INT_BIT_COUNT - bits.LeadingZeros(uint(maxx))
	for _, num := range nums {
		Insert(num)
	}
	for _, num := range nums {
		ans = max(ans, maxXor(num))
	}
	Clear()
	return ans
}
 
func maxXor(num int) int {
	// 最终异或的结果(尽量大)
	ans := 0
	treeIdx := 0
	status := 0 // num 某一位的状态
	want := 0   // num 某一位希望遇到的状态
	for i := high - 1; i >= 0; i-- {
		status = (num >> i) & 1
		want = status ^ 1
		if tree[treeIdx][want] == 0 {
			// 不能达成
			want ^= 1
		}
		// want 变成真的往下走的路
		ans |= (status ^ want) << i
		treeIdx = tree[treeIdx][want]
	}
	return ans
}
 
func Insert(num int) {
	treeIdx := 0
	for i := high - 1; i >= 0; i-- {
		idx := (num >> i) & 1
		if tree[treeIdx][idx] == 0 {
			tree[treeIdx][idx] = cnt
			cnt++
		}
		treeIdx = tree[treeIdx][idx]
	}
}
 
func Clear() {
	for i := 0; i < cnt; i++ {
		for j := 0; j < ROAD_COUNT; j++ {
			tree[i][j] = 0
		}
	}
	cnt = 1
}

哈希表的方法 §

思路和前缀树差不多

const (
	INT_BIT_COUNT = int(unsafe.Sizeof(int(0)) * 8) // int 占的位数
)
 
var (
	emptyStruct = struct{}{}
)
 
func findMaximumXOR(nums []int) int {
	ans := 0 // 自己可以异或自己，所以至少可以是 0
	set := map[int]struct{}{}
	maxx := 0
	for _, num := range nums {
		if num > maxx {
			maxx = num
		}
	}
	// 最高哪个位有 1
	high := INT_BIT_COUNT - bits.LeadingZeros(uint(maxx))
	for i := high - 1; i >= 0; i-- {
		// ans: 31...i+1 位都已经达成目标
		// 第 i 位能不能达成？
		better := ans | (1 << i) // 希望第 i 位能取 1
		clear(set)
		for _, num := range nums {
			// num: 保留 31...i 位的信息，低位刷成 0
			num = (num >> i) << i
			set[num] = emptyStruct
			// 如果 better^num 存在，说明 set 之前加过这样的数，设这个数为 x
			// better^num == x -> x^num == better
			// 即：better 能实现
			if _, has := set[better^num]; has {
				ans = better // 希望成真
				break
			}
			// else { ans 维持原状，即第 i 位还是 0 }
		}
	}
	return ans
}

复杂度 §

前缀树做法和哈希表做法复杂度都是一样的，只是哈希表做法常数更优

时间复杂度：$O(n\ast logV)$，空间复杂度：$O(n\ast logV)$，$V$ 是数值范围，$logV$ 的原因是遍历数值的二进制位

题目3.在二维字符数组中搜索可能的单词 §

题目描述 §

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] 是一个小写英文字母
• 1 <= words.length <= 3 * 10^4
• 1 <= words[i].length <= 10
• words[i] 由小写英文字母组成
• words 中的所有字符串互不相同

测试链接 §

212.单词搜索 II

答案 §

const (
	MAXN = 10001
)
 
var (
	tree = [MAXN][26]int{}
	pass = [MAXN]int{}
	// 前缀树的定制：不记录结尾的个数了，因为输入没有重复，个数始终为 1
	// 而是记录整个字符串是什么，方便直接收集
	end  = [MAXN]string{}
	cnt  = 1
 
	ans      []string
	theBoard [][]byte
	n        int
	m        int
)
 
func findWords(board [][]byte, words []string) []string {
	ans = []string{}
	n = len(board)
	if n == 0 {
		return ans
	}
	m = len(board[0])
	theBoard = board
	for _, word := range words {
		Insert(word)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			dfs(i, j, 0)
		}
	}
	Clear()
	return ans
}
 
// 来到了二维网格的 [i][j] 位置
// treeIdx: 当前来到的前缀树节点
// 返回值: 收集到了几个字符串
func dfs(i, j, treeIdx int) int {
	// 越界或之前走过
	if i < 0 || i == n || j < 0 || j == m || theBoard[i][j] == 0 {
		return 0
	}
 
	char := theBoard[i][j]
	treeIdx = tree[treeIdx][char-'a']
	if treeIdx == 0 {
		return 0
	}
	if pass[treeIdx] == 0 { // 剪枝
		return 0
	}
	// 从 [i][j] 出发，收集了几个字符串
	count := 0
	if end[treeIdx] != "" {
		count++
		ans = append(ans, end[treeIdx])
		end[treeIdx] = ""
	}
	// 标记 [i][j] 位置，防止下次再来到
	theBoard[i][j] = 0
	count += dfs(i-1, j, treeIdx)
	count += dfs(i+1, j, treeIdx)
	count += dfs(i, j-1, treeIdx)
	count += dfs(i, j+1, treeIdx)
	theBoard[i][j] = char
	pass[treeIdx] -= count // 为了剪枝
	return count
}
 
func Insert(word string) {
	n := len(word)
	treeIdx := 0
	pass[treeIdx]++
	for i := 0; i < n; i++ {
		idx := word[i] - 'a'
		if tree[treeIdx][idx] == 0 {
			tree[treeIdx][idx] = cnt
			cnt++
		}
		treeIdx = tree[treeIdx][idx]
		pass[treeIdx]++
	}
	end[treeIdx] = word
}
 
func Clear() {
	for i := 0; i < cnt; i++ {
		for j := 0; j < 26; j++ {
			tree[i][j] = 0
		}
		pass[i] = 0
		end[i] = ""
	}
	cnt = 1
}

复杂度 §

时间复杂度：$O(m\ast n\ast 4^{10})$

其中，$m\ast n$ 是二维网格大小，$4^{10}$ 是每个字符串最大长度是 10，每个字符都要向上下左右四个方向探索

不管用不用前缀树都是这个复杂度，只不过前缀树可以大量剪枝，优化常数时间

空间复杂度：$O(words中所有字符串的全部字符数量)$，前缀树的大小