2024-07-31: In go, given two arrays of positive integers arr1 and arr2, we want to find the length of all pairs (x, y) consisting of integer x belonging to arr1 and integer y belonging to arr2 that have the longest common prefix. The common prefix is the

2024-07-31: In go, given two arrays of positive integers arr1 and arr2, we want to find the length of all pairs (x, y) consisting of integer x belonging to arr1 and integer y belonging to arr2 that have the longest common prefix.

The common prefix is the part of the leftmost digit or digits of two numbers that are the same. For example, for the integers 5655359 and 56554, their common prefix is 565, while for 1223 and 43456, they have no common prefix.

We need to find out what is the length of all pairs of numbers (x, y) with the longest common prefix, and return 0 if there is no common prefix.

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

Output: 3

Explanation: There exist 3 pairs of numbers (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 public prefix is 100 and has a length of 3.

Answer 2024-07-31:

chatgpt

Title from leetcode3043.

The broad steps are as follows:

To solve the given problem, it is divided into the following broad steps:

Initialize a collection: Create a mapping (collection)hasFor storagearr1prefix of all integers in the set. This set will be used to subsequently find out if the integer is in thearr1A certain prefix in the
extract a prefix (linguistics): Iterationarr1in each integer, and for each integer, calculate each of its possible prefixes (i.e., divide the number by 10 bit by bit until the number is 0) and store each prefix in thehasin the set. This will allow thehasincludingarr1All prefixes for all numbers in the
Initialize a maximum value: Setting a variablemxfor recording in thearr2The largest public prefix found in the
Find public prefixes: Iterationarr2for each integer in the set, and for each integer, compute each of its possible prefixes (again dividing by 10 bit by bit), and add the prefixes to the set ofhasin the check to see if the prefix exists. If it exists, update themxis the prefix value of the current integer, as compared to the currently storedmxA comparison is made and the larger value is retained.
calculation result: InspectionmxIf the value ofmxis 0, indicating that no public prefix was found, and returns 0. Ifmxis not zero, compute its corresponding length, i.e.mxConverts to a string and takes its length, then returns that length as the result.
output result: Called through the main functionlongestCommonPrefixfunction, pass two arrays of integers, and print the length of the longest common prefix returned.

Time Complexity:

Iterate over the arrayarr1cap (a poem)arr2The time complexity is O(n * k), where n is the number ofarr2the length of the number, and k is the number of digits of the number (the number of iterations the prefix looks for). But since the number of digits of the number is finite, we can consider k as a constant. Thus the main complexity is caused by traversal, i.e. O(n).

Extra space complexity:

Using CollectionshasStoring prefixes, each integer has at most as many prefixes as its number of bits, so in the worst case, the space complexity is O(m * k), where m is the number ofarr1length of the digit, and k is the number of digits in the number of digits (which matches the number of prefixes). But since k is a constant, it can be simplified to O(m). Overall, this algorithm consumes O(m) extra in space.

The full Go code is below:

package main

import (
	"fmt"
	"strconv"
)

func longestCommonPrefix(arr1, arr2 []int) int {
	has := map[int]bool{}
	for _, v := range arr1 {
		for ; v > 0; v /= 10 {
			has[v] = true
		}
	}

	mx := 0
	for _, v := range arr2 {
		for ; v > 0 && !has[v]; v /= 10 {
		}
		mx = max(mx, v)
	}
	if mx == 0 {
		return 0
	}
	return len((mx))
}

func main() {
	arr1 := []int{1, 10, 100}
	arr2 := []int{1000}
	(longestCommonPrefix(arr1, arr2))
}

在这里插入图片描述

The full Python code is below:

# -*-coding:utf-8-*-

def longest_common_prefix(arr1, arr2):
    has = set()
    
    # commander-in-chief (military) arr1 Each prefix of all numbers in the set is added to the set
    for v in arr1:
        while v > 0:
            (v)
            v //= 10
    
    mx = 0
    
    # exist arr2 Finding the greatest connection with arr1 Numbers with the same prefix
    for v in arr2:
        while v > 0 and v not in has:
            v //= 10
        mx = max(mx, v)
    
    if mx == 0:
        return 0
    
    return len(str(mx))

if __name__ == "__main__":
    arr1 = [1, 10, 100]
    arr2 = [1000]
    print(longest_common_prefix(arr1, arr2))

在这里插入图片描述