最长公共前缀的长度

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.

 

Example 1:

Input: arr1 = [1,10,100], arr2 = [1000]
Output: 3
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: 0
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.

 

Constraints:

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

/*
题目思路：
1. 使用 Java Stream 遍历两个数组的所有数对。
2. 对每一个数对计算公共前缀长度。
3. 找出最长的公共前缀长度。
*/

import java.util.Arrays;

public class LongestCommonPrefixStream {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        return Arrays.stream(arr1)
                      .flatMap(x -> Arrays.stream(arr2).mapToObj(y -> commonPrefixLength(x, y)))
                      .max(Integer::compareTo)
                      .orElse(0);
    }

    private int commonPrefixLength(int x, int y) {
        String s1 = String.valueOf(x);
        String s2 = String.valueOf(y);
        int minLength = Math.min(s1.length(), s2.length());
        int length = 0;
        for (int i = 0; i < minLength; i++) {
            if (s1.charAt(i) == s2.charAt(i)) {
                length++;
            } else {
                break;
            }
        }
        return length;
    }

    public static void main(String[] args) {
        LongestCommonPrefixStream lcp = new LongestCommonPrefixStream();
        int[] arr1 = {1, 10, 100};
        int[] arr2 = {1000};
        System.out.println(lcp.longestCommonPrefix(arr1, arr2));  // 输出: 3
    }
}

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

O(n)

O(n)