Find Length of Longest Common Prefix — Digit Trie
Sanjeev SharmaAdvertisement
Problem
Find the longest common prefix (as string of digits) between any number in arr1 and any number in arr2.
Solutions
Python
class Solution:
def longestCommonPrefix(self, arr1: list[int], arr2: list[int]) -> int:
root={}
for n in arr1:
node=root
for c in str(n):
if c not in node: node[c]={}
node=node[c]
ans=0
for n in arr2:
node=root; cur=0
for c in str(n):
if c not in node: break
node=node[c]; cur+=1; ans=max(ans,cur)
return ans
Complexity
- Time: O(n * D) where D = digits | Space: O(n * D)
Advertisement
