→ SecondRun: 大師 09/24 20:49
推 orangeNoob: 別捲了 09/24 20:50
→ sixB: 你好厲害 09/24 20:51
推 dont: 大師 09/24 23:26
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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.150.186 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727182134.A.2FB.html