class Solution {
public:
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
}
};
100229. 最长公共前缀的长度
给你两个 正整数 数组 arr1 和 arr2 。
正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是 。
设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 ，而 1223 和 43456 没有 公共前缀。
你需要找出属于 arr1 的整数 x 和属于 arr2 的整数 y 组成的所有数对 (x, y) 之中最长的公共前缀的长度。
返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀，则返回 0 。
示例 1：
输入：arr1 = [1,10,100], arr2 = [1000] 输出：3 解释：存在 3 个数对 (arr1[i], arr2[j]) ： - (1, 1000) 的最长公共前缀是 1 。 - (10, 1000) 的最长公共前缀是 10 。 - (100, 1000) 的最长公共前缀是 100 。 最长的公共前缀是 100 ，长度为 3 。
示例 2：
输入：arr1 = [1,2,3], arr2 = [4,4,4] 输出：0 解释：任何数对 (arr1[i], arr2[j]) 之中都不存在公共前缀，因此返回 0 。 请注意，同一个数组内元素之间的公共前缀不在考虑范围内。
提示：
1 <= arr1.length, arr2.length <= 5 * 1041 <= arr1[i], arr2[i] <= 108原站题解
golang 解法, 执行用时: 158 ms, 内存消耗: 9.3 MB, 提交时间: 2024-02-19 11:35:59
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(strconv.Itoa(mx))
}
// 用字符串处理
func longestCommonPrefix2(arr1, arr2 []int) (ans int) {
has := map[string]bool{}
for _, x := range arr1 {
s := strconv.Itoa(x)
for i := 1; i <= len(s); i++ {
has[s[:i]] = true
}
}
for _, x := range arr2 {
s := strconv.Itoa(x)
for i := 1; i <= len(s) && has[s[:i]]; i++ {
ans = max(ans, i)
}
}
return
}
python3 解法, 执行用时: 508 ms, 内存消耗: 28.6 MB, 提交时间: 2024-02-19 11:35:29
class Solution:
# 用字符串处理
def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
st = set()
for s in map(str, arr1):
for i in range(1, len(s) + 1):
st.add(s[:i])
ans = 0
for s in map(str, arr2):
for i in range(1, len(s) + 1):
if s[:i] not in st:
break
ans = max(ans, i)
return ans
# 用整数处理
def longestCommonPrefix2(self, arr1: List[int], arr2: List[int]) -> int:
st = set()
for x in arr1:
while x:
st.add(x)
x //= 10
mx = 0
for x in arr2:
while x and x not in st:
x //= 10
mx = max(mx, x)
return len(str(mx)) if mx else 0