Given two arrays of numbers, Return the length of the longest common prefix between any pair of numb-CodePudding

Given two arrays of numbers, first Array and second Array. Return the length of the longest common prefix (LCP) between any pair of numbers from different arrays or 0 if no common prefix exists.

Note: A prefix of a number is a number formed by one or more of its digits, starting from its highest-order digit. For example, 123 is a prefix of the number 12345 and 2 is a prefix of the number 234. A common prefix of two numbers is a number, which is a prefix of both. For instance, longest common prefix (LCP) of 5655359 and 56554 is 5655 and there is no common prefix of 123 and 456

Example • For firstArray = [25, 288, 2655, 54546, 54, 555] and secondArray = [2, 255, 266, 244, 26, 5, 54547] , the output should be solution (firstArray, secondArray)= 4

Explanation: The best pair is 54546 from first array and 54547 from second array. The LCP is 5454 of length 4.

Here is what I have tried:

firstArray = [25, 288, 2655, 54546, 54, 555]

secondArray = [2, 255, 266, 244, 26, 5, 54547]

firstArray = [str(n) for n in firstArray]
secondArray = [str(n) for n in secondArray]
for i in range(len(firstArray)):
  for j in range(len(secondArray)):
    if secondArray[j].startswith(firstArray[i]):
      x = firstArray[i]
      print(len(x))

CodePudding user response：

To find the length of the longest common prefix between any pair of numbers from different arrays, you can use the following steps:

Initialize a variable to store the maximum prefix length as 0. Iterate through the first array and for each element, compare it with each element in the second array. For each pair of elements, find the common prefix between them by comparing their digits one by one starting from the leftmost digit. Keep track of the length of the common prefix. Compare the length of the current common prefix with the maximum prefix length stored in the variable. If it is greater, update the maximum prefix length variable with the current length. Repeat steps 2-4 for all pairs of elements from different arrays. Return the maximum prefix length variable at the end. Note: The above steps can be implemented in any programming language of your choice like Python, Java, C etc.

Here is an example of how this function could be implemented in Python:def longestCommonPrefix(arr1, arr2): max_prefix_length = 0 for num1 in arr1: for num2 in arr2: prefix_length = 0 for i in range(min(len(str(num1)), len(str(num2)))): if str(num1)[i] == str(num2)[i]: prefix_length = 1 else: break max_prefix_length = max(max_prefix_length, prefix_length) return max_prefix_length ``

CodePudding user response：

First, you aren't calculating the common prefix correctly. One way of doing this is to iterate over a pair's characters and track when they stop being equal:

def common_prefix(s1, s2):
    common_len = min(len(s1), len(s2))
    for i in range(common_len):
        if s1[i] != s2[i]:
            return i
    return common_len

Once you have that, you can take the product of the two lists, and return the maximal common prefix of each two items:

from itertools import product
result = max(common_prefix(p[0], p[1]) for p in product((str(s) for s in firstArray), (str(s) for s in secondArray)))