Show problems as
Classic problem #3043MediumArrayHash TableStringTrie

Find the Length of the Longest Common Prefix

Real-world version: Longest Shared Route Lead
Tracked in this browser only
Read Find the Length of the Longest Common Prefix on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A courier network stamps every parcel with a numeric routing code, written in decimal with no leading zeros. A code is read from the left: the first digit names the region, the digit after it names a depot inside that region, and so on down to the delivery walk. Two codes therefore travel together for as far as their leading digits agree.

You are given two arrays of routing codes, northern and southern. Take one code from northern and one from southern. Their shared lead is how many digits they agree on, counting from the leftmost digit and stopping at the first position where they differ or where either code runs out of digits.

Return the longest shared lead over every way of pairing one code from northern with one code from southern. If no such pairing agrees on even its leftmost digit, return 0.

Examples

Example 1

Input
northern = [917, 91, 4], southern = [9174, 63]
Output
3

Pairing 917 with 9174 agrees on the digits 9, 1 and 7, then 9174 still has a digit left while 917 has run out, so that pairing has a shared lead of 3.

Example 2

Input
northern = [52, 61], southern = [7, 8]
Output
0

Every pairing differs at the leftmost digit, so no pairing has a shared lead at all.

Example 3

Input
northern = [8, 80], southern = [8888, 800]
Output
2

Pairing 80 with 800 agrees on the digits 8 and 0, and 80 then runs out, giving a shared lead of 2.

Constraints

  • 1 <= northern.length, southern.length <= 5 * 10^4
  • 1 <= northern[i], southern[i] <= 10^8
  • Codes are written in decimal without leading zeros

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_shared_lead(northern: list[int], southern: list[int]) -> int:
Java
public int longestSharedLead(int[] northern, int[] southern)

More on the same topics