3043 最长公共前缀的长度-中等

题目：

给你两个 正整数 数组 arr1 和 arr2 。

正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是 。

设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 ，而 1223 和 43456 没有 公共前缀。

你需要找出属于 arr1 的整数 x 和属于 arr2 的整数 y 组成的所有数对 (x, y) 之中最长的公共前缀的长度。

返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀，则返回 0 。

示例 1：

输入：arr1 = [1,10,100], arr2 = [1000]
输出：3
解释：存在 3 个数对 (arr1[i], arr2[j]) ：
- (1, 1000) 的最长公共前缀是 1 。
- (10, 1000) 的最长公共前缀是 10 。
- (100, 1000) 的最长公共前缀是 100 。
最长的公共前缀是 100 ，长度为 3 。

示例 2：

输入：arr1 = [1,2,3], arr2 = [4,4,4]
输出：0
解释：任何数对 (arr1[i], arr2[j]) 之中都不存在公共前缀，因此返回 0 。
请注意，同一个数组内元素之间的公共前缀不在考虑范围内。

解题思路

将其中一个数组进行字典树构建，然后后另一个数组在字典树进行查找，并找到最长的公共前缀长度。

// date 2024/03/31
type Trie struct {
	child [10]*Trie
}

func NewTrie() *Trie {
	return &Trie{child: [10]*Trie{}}
}

func (this *Trie) insert(num string) {
	cur := this
	n := len(num)
	for i := 0; i < n; i++ {
		idx := num[i] - '0'
		if cur.child[idx] == nil {
			cur.child[idx] = NewTrie()
		}
		cur = cur.child[idx]
	}
}

func (this *Trie) searchPrefix(prefix string) int {
	cur := this
	n := len(prefix)
	ans := 0
	for i := 0; i < n; i++ {
		idx := prefix[i] - '0'
		if cur.child[idx] != nil {
			cur = cur.child[idx]
			ans++
		} else {
			break
		}
	}
	return ans
}

func longestCommonPrefix(arr1 []int, arr2 []int) int {
	tie := NewTrie()
	ans := 0

	for _, v := range arr1 {
		tie.insert(fmt.Sprintf("%d", v))
	}
	for _, v := range arr2 {
		temp := tie.searchPrefix(fmt.Sprintf("%d", v))
		ans = max(ans, temp)
	}

	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}