3043. Find the Length of the Longest Common Prefix
给两个正整数矩阵arr1、arr2
从arr1和arr2个挑一个正整数出来
请问在所有配对中，最长的prefix是多少位?
思路:
就把其中一个矩阵变成字典树
再来去遍历另外一个矩阵，找最长的prefix就好
没什么难度
golang code :
type trie struct {
child [10]*trie
}
func longestCommonPrefix(arr1 []int, arr2 []int) int {
trie_tree := trie{[10]*trie{}}
res:=0
for _, val := range arr2 {
s := strconv.Itoa(val)
insert(s, &trie_tree)
}
for _, val := range arr1 {
s := strconv.Itoa(val)
a := search(s, &trie_tree)
res=max(res,a)
}
return res
}
func insert(s string, tree *trie) {
n := len(s)
for i := 0; i < n; i++ {
idx := int(s[i] - '0')
if tree.child[idx] == nil {
tree.child[idx] = &trie{[10]*trie{}}
}
tree = tree.child[idx]
}
}
func search(s string, tree *trie) int {
n := len(s)
res := 0
for i := 0; i < n; i++ {
idx := int(s[i] - '0')
if tree.child[idx] == nil {
break
}
tree = tree.child[idx]
res++
}
return res
}