Problem: 100229. 最长公共前缀的长度

[TOC]

思路

根据 arr1 构建一棵 Trie 树，在树里查找 arr2

Code

###Go

func longestCommonPrefix(arr1 []int, arr2 []int) int {
if len(arr1) > len(arr2) {
    arr2, arr1 = arr1, arr2
}
trie := Constructor()
for i := range arr1 {
trie.Insert(strconv.Itoa(arr1[i]))
}
maxLen := 0
for i := range arr2 {
s := strconv.Itoa(arr2[i])
        maxLen = max(maxLen, trie.GetCommonLen(s))
}
return maxLen
}

type Trie struct {
child [10]*Trie
}

func Constructor() Trie {
return Trie{}
}

func (this *Trie) Insert(word string) {
node := this
for _, i := range word {
i -= '0'
if node.child[i] == nil {
node.child[i] = &Trie{}
}
node = node.child[i]
}
}

func (this *Trie) GetCommonLen(prefix string) int {
node := this
for i, c := range prefix {
c -= '0'
if node.child[c] == nil {
return i
}
node = node.child[c]
}
return len(prefix)
}