Coinbase

01Find the Length of the Longest Common Prefix

You are given two arrays with positive integers arr1 and arr2. A prefix of a positive integer is an integer formed by one or more of its digits, starting from its leftmost digit. For example, 123 is a prefix of the integer 12345, while 234 is not. A common prefix of two integers a and b is an integer c, such that c is a prefix of both a and b. For example, 5655359 and 56554 have a common prefix 565 while 1223 and 43456 do not have a common prefix. You need to find the length of the longest common prefix between all pairs of integers (x, y) such that x belongs to arr1 and y belongs to arr2. Return the length of the longest common prefix among all pairs. If no common prefix exists among them, return 0.

Constraints

1 ≤ arr1.length, arr2.length ≤ 5 * 10⁴
1 ≤ arr1[i], arr2[i] ≤ 10⁸

Example 1

Input:

arr1 = [1,10,100]
arr2 = [1000]

Output:

Explanation: There are 3 pairs (arr1[i], arr2[j]):

The longest common prefix of (1, 1000) is 1.
The longest common prefix of (10, 1000) is 10.
The longest common prefix of (100, 1000) is 100. The longest common prefix is 100 with a length of 3.

Example 2

Input:

arr1 = [1,2,3]
arr2 = [4,4,4]

Output:

Explanation: There exists no common prefix for any pair (arr1[i], arr2[j]), hence we return 0. Note that common prefixes between elements of the same array do not count.

解法

用 Trie 思路的等价 HashSet 加速：先把 arr1 中每个数的所有前缀(按字符串前缀切片)放入哈希集合；再遍历 arr2，对每个数的所有前缀检查是否出现在集合中，更新最长匹配长度。时间复杂度 O((m + n)·L)，L 为数字位数(≤ 10)，空间复杂度 O(m·L)。

from typing import List

def longestCommonPrefix(arr1: List[int], arr2: List[int]) -> int:
    prefixes = set()
    for x in arr1:
        s = str(x)
        for i in range(1, len(s) + 1):
            prefixes.add(s[:i])
    ans = 0
    for y in arr2:
        s = str(y)
        for i in range(1, len(s) + 1):
            if s[:i] in prefixes:
                ans = max(ans, i)
    return ans

class Solution {
    int longestCommonPrefix(int[] arr1, int[] arr2) {
        Set<String> prefixes = new HashSet<>();
        for (int x : arr1) {
            String s = Integer.toString(x);
            for (int i = 1; i <= s.length(); i++) {
                prefixes.add(s.substring(0, i));
            }
        }
        int ans = 0;
        for (int y : arr2) {
            String s = Integer.toString(y);
            for (int i = 1; i <= s.length(); i++) {
                if (prefixes.contains(s.substring(0, i))) {
                    ans = Math.max(ans, i);
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
        unordered_set<string> prefixes;
        for (int x : arr1) {
            string s = to_string(x);
            for (int i = 1; i <= (int)s.size(); i++) {
                prefixes.insert(s.substr(0, i));
            }
        }
        int ans = 0;
        for (int y : arr2) {
            string s = to_string(y);
            for (int i = 1; i <= (int)s.size(); i++) {
                if (prefixes.count(s.substr(0, i))) {
                    ans = max(ans, i);
                }
            }
        }
        return ans;
    }
};