3043. Find the Length of the Longest Common Prefix
## 思路
先對arr1建TrieTree, 再查找arr2的字在TrieTree裡的LCP
## Code
```python
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
class TrieTree:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
curr = self.root
for ch in word:
if ch not in curr.children:
curr.children[ch] = TrieNode()
curr = curr.children[ch]
curr.is_word = True
def search(self, word):
res = 0
curr = self.root
for ch in word:
if ch not in curr.children:
break
curr = curr.children[ch]
res += 1
return res
class Solution:
def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
trie = TrieTree()
for num in arr1:
trie.insert(str(num))
res = 0
for num in arr2:
res = max(res, trie.search(str(num)))
return res
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.164 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727191565.A.C86.html