本文主要是介绍Leetcode 3043. Find the Length of the Longest Common Prefix，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- Leetcode 3043. Find the Length of the Longest Common Prefix
- 1. 解题思路
- 2. 代码实现
- 题目链接：3043. Find the Length of the Longest Common Prefix
1. 解题思路
这一题其实暴力求解也问题不大，只要把一个数列当中所有数字所能构成的prefix全部记录下来，然后在另一个arr当中进行查找就行。
不过，这里一个更为优雅的实现是使用Trie树的方式，我们用一个数组来构造一个Trie树，然后遍历另一个数组，找到每一个数字在Trie树当中的最长公共前缀，然后进行返回即可。
两者本质上是完全一样的，不过后者思路和实现上更加优雅一些。
2. 代码实现
给出python代码实现如下：
class Trie:def __init__(self):self.trie = {}def add_word(self, word):trie = self.triefor c in word:trie = trie.setdefault(c, {})trie["eos"] = wordreturndef find_prefix(self, word):trie = self.trielength = 0for c in word:if c not in trie:breaktrie = trie[c]length += 1return lengthclass Solution:def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:trie = Trie()for x in arr1:trie.add_word(str(x))return max(trie.find_prefix(str(x)) for x in arr2)
提交代码评测得到：耗时818ms，占用内存36.6MB。
这篇关于Leetcode 3043. Find the Length of the Longest Common Prefix的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
