跳转至

3043. 最长公共前缀的长度

题目描述

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

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

设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 和 5655，而 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

解法

方法一：哈希表

我们可以使用哈希表来存储 arr1 中的所有数字的前缀，然后遍历 arr2 中的所有数字 \(x\)，对于每个数字 \(x\)，我们从最高位开始逐渐减小，判断是否存在于哈希表中，如果存在，那么我们就找到了一个公共前缀，此时更新答案即可。

时间复杂度 \(O(m \times \log M + n \times \log N)\)，空间复杂度 \(O(m \times \log M)\)。其中 \(m\) 和 \(n\) 分别是 arr1 和 arr2 的长度，而 \(M\) 和 \(N\) 分别是 arr1 和 arr2 中的最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        s = set()
        for x in arr1:
            while x:
                s.add(x)
                x //= 10
        mx = 0
        for x in arr2:
            while x:
                if x in s:
                    mx = max(mx, x)
                    break
                x //= 10
        return len(str(mx)) if mx else 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        Set<Integer> s = new HashSet<>();
        for (int x : arr1) {
            for (; x > 0; x /= 10) {
                s.add(x);
            }
        }
        int mx = 0;
        for (int x : arr2) {
            for (; x > 0; x /= 10) {
                if (s.contains(x)) {
                    mx = Math.max(mx, x);
                    break;
                }
            }
        }
        return mx > 0 ? String.valueOf(mx).length() : 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
        unordered_set<int> s;
        for (int x : arr1) {
            for (; x; x /= 10) {
                s.insert(x);
            }
        }
        int mx = 0;
        for (int x : arr2) {
            for (; x; x /= 10) {
                if (s.count(x)) {
                    mx = max(mx, x);
                    break;
                }
            }
        }
        return mx > 0 ? (int) log10(mx) + 1 : 0;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func longestCommonPrefix(arr1 []int, arr2 []int) int {
    s := map[int]bool{}
    for _, x := range arr1 {
        for ; x > 0; x /= 10 {
            s[x] = true
        }
    }
    mx := 0
    for _, x := range arr2 {
        for ; x > 0; x /= 10 {
            if s[x] {
                mx = max(mx, x)
                break
            }
        }
    }
    if mx > 0 {
        return len(strconv.Itoa(mx))
    }
    return 0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function longestCommonPrefix(arr1: number[], arr2: number[]): number {
    const s: Set<number> = new Set<number>();
    for (let x of arr1) {
        for (; x; x = Math.floor(x / 10)) {
            s.add(x);
        }
    }
    let mx: number = 0;
    for (let x of arr2) {
        for (; x; x = Math.floor(x / 10)) {
            if (s.has(x)) {
                mx = Math.max(mx, x);
                break;
            }
        }
    }
    return mx > 0 ? Math.floor(Math.log10(mx)) + 1 : 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
impl Solution {
    pub fn longest_common_prefix(arr1: Vec<i32>, arr2: Vec<i32>) -> i32 {
        let mut s = std::collections::HashSet::new();
        for x in arr1 {
            let mut y = x;
            while y > 0 {
                s.insert(y);
                y /= 10;
            }
        }
        let mut mx = 0;
        for x in arr2 {
            let mut y = x;
            while y > 0 {
                if s.contains(&y) {
                    mx = mx.max(y);
                    break;
                }
                y /= 10;
            }
        }
        if mx > 0 {
            (mx as f64).log10().floor() as i32 + 1
        } else {
            0
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number}
 */
var longestCommonPrefix = function (arr1, arr2) {
    const s = new Set();
    for (let x of arr1) {
        for (; x; x = Math.floor(x / 10)) {
            s.add(x);
        }
    }
    let mx = 0;
    for (let x of arr2) {
        for (; x; x = Math.floor(x / 10)) {
            if (s.has(x)) {
                mx = Math.max(mx, x);
                break;
            }
        }
    }
    return mx > 0 ? Math.floor(Math.log10(mx)) + 1 : 0;
};

评论