最长公共前缀的长度

标签: 字典树 数组 哈希表 字符串

难度: Medium

给你两个 正整数 数组 arr1 和 arr2 。

正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是 。

设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 ，而 1223 和 43456 没有 公共前缀。

你需要找出属于 arr1 的整数 x 和属于 arr2 的整数 y 组成的所有数对 (x, y) 之中最长的公共前缀的长度。

返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀，则返回 0 。

示例 1：

输入：arr1 = [1,10,100], arr2 = [1000]
输出：3
解释：存在 3 个数对 (arr1[i], arr2[j]) ：
- (1, 1000) 的最长公共前缀是 1 。
- (10, 1000) 的最长公共前缀是 10 。
- (100, 1000) 的最长公共前缀是 100 。
最长的公共前缀是 100 ，长度为 3 。

示例 2：

输入：arr1 = [1,2,3], arr2 = [4,4,4]
输出：0
解释：任何数对 (arr1[i], arr2[j]) 之中都不存在公共前缀，因此返回 0 。
请注意，同一个数组内元素之间的公共前缀不在考虑范围内。

提示：

  • 1 <= arr1.length, arr2.length <= 5 * 104
  • 1 <= arr1[i], arr2[i] <= 108

Submission

运行时间: 144 ms

内存: 29.0 MB

class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        s1 = set()
        s2 = set()
        for x in arr1:
            while x and x not in s1:
                s1.add(x)
                x //= 10
        for x in arr2:
            while x and x not in s2:
                s2.add(x)
                x //= 10
        u = s1 & s2
        return len(str(max(u))) if u else 0

Explain

这个问题的解决方案首先是构建两个集合s1和s2，用于存储arr1和arr2中所有可能的前缀。对于每个元素，我们通过逐步除以10（去掉最右边的数字）来获取所有前缀，并将其添加到相应的集合中。这样，每个集合都会包含其数组中所有数字的所有前缀。接下来，我们取两个集合的交集，找出同时出现在两个数组中的前缀。最后，从交集中选择最长的前缀（如果存在的话），并返回其长度。如果交集为空，说明没有公共前缀，返回0。

时间复杂度: O(n)

空间复杂度: O(n)

# 类定义

class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        s1 = set()  # 存储arr1中所有数字的前缀
        s2 = set()  # 存储arr2中所有数字的前缀
        for x in arr1:  # 遍历arr1中的每一个数字
            while x and x not in s1:  # 将数字的每个前缀加入s1，直到x为0或已存在于集合中
                s1.add(x)
                x //= 10  # 移除数字的最后一位
        for x in arr2:  # 遍历arr2中的每一个数字
            while x and x not in s2:  # 将数字的每个前缀加入s2，直到x为0或已存在于集合中
                s2.add(x)
                x //= 10  # 移除数字的最后一位
        u = s1 & s2  # 找出两个集合的交集
        return len(str(max(u))) if u else 0  # 返回最长公共前缀的长度，如果没有公共前缀则返回0

Explore

在代码中，s1和s2是集合数据结构，它们的特性是自动去除重复元素。因此，即使尝试多次添加相同的前缀，集合仍然只保留一个。这样，不会有重复的前缀存在于集合中。这种特性有助于保持集合的唯一性，不会影响算法的正确性。同时，使用集合可以避免重复检查，从而在一定程度上提高效率。

构建前缀集合时，继续添加前缀直到`x为0`是为了确保捕获从最长到最短的所有可能前缀。这种方法简单且直接，确保了所有前缀都被考虑。然而，对于提高效率，一种可能的方法是在添加前缀前先检查这个前缀是否已经存在于集合中，如果存在，则不再继续对该数字进行处理。这样可以减少不必要的除法和添加操作，尤其是在处理较大数字时。

对于数组为空的情况，应在函数开始时进行检查。如果任一数组为空，则没有公共前缀，应立即返回0。对于数组中所有元素都是相同的数字的情况，由于这些元素具有相同的前缀，所以最长公共前缀就是任一元素本身的长度。因此，这种情况下算法仍然有效，可以正确返回最长公共前缀的长度。