题目描述#

咱来翻译下题面：给定两个正整数数组 arr1 和 arr2，要从 arr1 中选一个数 x，从 arr2 中选一个数 y，看它们从最左边开始能匹配多少位数字。

一个整数的前缀必须从第一位开始连续取，比如 123 是 12345 的前缀，但 234 不是。现在要在所有 (x, y) 数对里，找出最长公共前缀的长度；如果完全没有公共前缀，就返回 0。

思路#

这题一眼看过去像是要建 Trie，毕竟关键词都写着“前缀”了嘛。不过你给的这份代码走的是更轻巧的做法：把 arr1 中所有数字的所有前缀都存进哈希表，再拿 arr2 的前缀去查。

先遍历 arr1。每个整数转成字符串 s 后，枚举 s[:1]、s[:2]、一直到整个 s，这些都代表这个数的合法前缀。把它们放进 hp 里，就等于提前准备好了一本“前缀相册”：之后只要查某个前缀有没有出现过，就能 O(1) 判断它是否是某个 arr1 数字的前缀。

接着遍历 arr2。同样把每个数转成字符串，从短到长枚举它的前缀。只要当前前缀还在 hp 里，就说明它能和某个 arr1 的数形成公共前缀，于是更新答案长度。遇到第一个不存在的前缀就可以停下，因为更长的前缀一定包含这个已经失败的短前缀，不可能突然又匹配上。

所以这题的类型可以归到 字典树思想 / 前缀匹配，实现方式则是 哈希表枚举前缀。哼哼，不一定非要真的画一棵树；有时候把所有路径拍成照片存起来，也能很快认出熟面孔哦。

时间复杂度是 O(D)，其中 D 是两个数组中所有数字的位数总和；空间复杂度也是 O(D)，用于保存 arr1 产生的所有前缀。

知识边界#

• 本题核心是前缀匹配，可以用 Trie，也可以像这份代码一样用哈希表保存所有前缀。
• 公共前缀必须从数字最左侧开始连续匹配，不能只找中间某段相同数字。
• 检查 arr2 时遇到第一个不存在的前缀就能停止，因为更长前缀不可能绕过前面失败的位置。
• 数字先转成字符串后再切前缀，逻辑最直接；本题比较的是数字的十进制表示，不是数值大小。
• 代码里使用了 Go 的内置 max；如果运行环境较旧，需要改成普通的 if i > ans { ans = i }，不过这里咱保留原写法。

代码#

import "strconv"

func longestCommonPrefix(arr1 []int, arr2 []int) int {
	hp := make(map[string]bool)
	for _, x := range arr1 {
		s := strconv.Itoa(x)
		for i := 1; i <= len(s); i++ {
			hp[s[:i]] = true
		}
	}
	ans := 0
	for _, x := range arr2 {
		s := strconv.Itoa(x)
		for i := 1; i <= len(s) && hp[s[:i]]; i++ {
			ans = max(ans, i)
		}
	}
	return ans
}