Re: [閒聊] 每日leetcode
看板Marginalman作者DJYOSHITAKA (franchouchouISBEST)時間1年前 (2024/09/24 23:35)推噓2(2推 0噓 1→)留言3則, 3人參與討論串903/1554 (看更多)
就用trie
不過速度很慢 不知道又怎麼了
板友 救救字典樹
class Node:
def __init__(self):
self.child = [None for _ in range(10)]
class Solution:
def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
# build trie for arr1
root = Node()
for num in arr1:
s = str(num)
cur = root
for c in s:
if cur.child[ord(c)-ord('0')] is None:
cur.child[ord(c)-ord('0')] = Node()
cur = cur.child[ord(c)-ord('0')]
# inference
ans = 0
for num in arr2:
s = str(num)
cur, cur_len = root, 0
for c in s:
if cur.child[ord(c)-ord('0')] is not None:
cur_len += 1
cur = cur.child[ord(c)-ord('0')]
else:
break
ans = max(ans, cur_len)
return ans
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727192148.A.8F2.html
推
09/24 23:40,
1年前
, 1F
09/24 23:40, 1F
→
09/24 23:41,
1年前
, 2F
09/24 23:41, 2F
推
09/25 00:56,
1年前
, 3F
09/25 00:56, 3F
討論串 (同標題文章)
完整討論串 (本文為第 903 之 1554 篇)：