Re: [閒聊] 每日leetcode
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
→
09/24 20:49,
1年前
, 1F
09/24 20:49, 1F
推
09/24 20:50,
1年前
, 2F
09/24 20:50, 2F
→
09/24 20:51,
1年前
, 3F
09/24 20:51, 3F
推
09/24 23:26,
1年前
, 4F
09/24 23:26, 4F
討論串 (同標題文章)
完整討論串 (本文為第 901 之 1554 篇)：