就用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