find-the-length-of-the-longest-common-prefix

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given two arrays with positive integers <code>arr1</code> and <code>arr2</code>.

A prefix of a positive integer is an integer formed by one or more of its digits, starting from its leftmost digit. For example, <code>123</code> is a prefix of the integer <code>12345</code>, while <code>234</code> is not.

A common prefix of two integers <code>a</code> and <code>b</code> is an integer <code>c</code>, such that <code>c</code> is a prefix of both <code>a</code> and <code>b</code>. For example, <code>5655359</code> and <code>56554</code> have common prefixes <code>565</code> and <code>5655</code> while <code>1223</code> and <code>43456</code> do not have a common prefix.

You need to find the length of the longest common prefix between all pairs of integers <code>(x, y)</code> such that <code>x</code> belongs to <code>arr1</code> and <code>y</code> belongs to <code>arr2</code>.

Return the length of the longest common prefix among all pairs. If no common prefix exists among them, return <code>0</code>.

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:

<pre>
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= arr1.length, arr2.length &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= arr1[i], arr2[i] &lt;= 108</code></li>
</ul>

longestCommonPrefix

Find the Length of the Longest Common Prefix

Longest Common Prefix

longest-common-prefix

最长公共前缀

Longest Common Suffix Queries

longest-common-suffix-queries

最长公共后缀查询

Trie

Array

Hash Table

String

给你两个 正整数 数组 <code>arr1</code> 和 <code>arr2</code> 。

正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如，<code>123</code> 是整数 <code>12345</code> 的前缀，而 <code>234</code> 不是 。

设若整数 <code>c</code> 是整数 <code>a</code> 和 <code>b</code> 的 公共前缀 ，那么 <code>c</code> 需要同时是 <code>a</code> 和 <code>b</code> 的前缀。例如，<code>5655359</code> 和 <code>56554</code> 有公共前缀 <code>565</code>&nbsp;和 <code>5655</code>，而 <code>1223</code> 和 <code>43456</code> 没有 公共前缀。

你需要找出属于 <code>arr1</code> 的整数 <code>x</code> 和属于 <code>arr2</code> 的整数 <code>y</code> 组成的所有数对 <code>(x, y)</code> 之中最长的公共前缀的长度。

返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀，则返回 <code>0</code> 。

&nbsp;

示例 1：

<pre>
输入：arr1 = [1,10,100], arr2 = [1000]
输出：3
解释：存在 3 个数对 (arr1[i], arr2[j]) ：
- (1, 1000) 的最长公共前缀是 1 。
- (10, 1000) 的最长公共前缀是 10 。
- (100, 1000) 的最长公共前缀是 100 。
最长的公共前缀是 100 ，长度为 3 。
</pre>

示例 2：

<pre>
输入：arr1 = [1,2,3], arr2 = [4,4,4]
输出：0
解释：任何数对 (arr1[i], arr2[j]) 之中都不存在公共前缀，因此返回 0 。
请注意，同一个数组内元素之间的公共前缀不在考虑范围内。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= arr1.length, arr2.length &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= arr1[i], arr2[i] &lt;= 108</code></li>
</ul>