Hard
题目描述
在一个有 n 个城市的国家中，城市编号为 0 到 n - 1。在这个国家中，每对城市之间都有道路连接。
有 m 个朋友，编号为 0 到 m - 1，他们在这个国家中旅行。每个朋友都会走一条由一些城市组成的路径。每条路径都用一个整数数组表示，数组中包含按顺序访问的城市。路径可能包含同一个城市多次，但同一个城市不会连续出现。
给定一个整数 n 和一个二维整数数组 paths，其中 paths[i] 是表示第 i 个朋友路径的整数数组，返回所有朋友路径共享的最长公共子路径的长度，如果没有公共子路径则返回 0。
路径的子路径是该路径中连续的城市序列。
示例 1：
输入：n = 5, paths = [[0,1,2,3,4],
[2,3,4],
[4,0,1,2,3]]
输出：2
解释：最长公共子路径是 [2,3]。
示例 2：
输入：n = 3, paths = [[0],[1],[2]]
输出：0
解释：三条路径没有共享的公共子路径。
示例 3：
输入：n = 5, paths = [[0,1,2,3,4],
[4,3,2,1,0]]
输出：1
解释：可能的最长公共子路径是 [0]、[1]、[2]、[3] 和 [4]。长度都为 1。
约束条件：
- 1 <= n <= 10^5
- m == paths.length
- 2 <= m <= 10^5
- sum(paths[i].length) <= 10^5
- 0 <= paths[i][j] < n
- 在 paths[i] 中，同一个城市不会连续多次出现
解题思路
这道题要求找到所有路径的最长公共子路径，可以使用二分搜索 + 滚动哈希的方法。
核心思路：
二分搜索长度：如果长度为 x 的公共子路径存在，那么长度小于 x 的公共子路径也必然存在。因此可以二分搜索答案的长度。
滚动哈希验证：对于每个候选长度 mid，需要验证是否存在长度为 mid 的公共子路径。使用滚动哈希计算所有长度为 mid 的子路径的哈希值，如果某个哈希值在所有路径中都出现，则存在公共子路径。
哈希函数选择：为了避免哈希冲突，使用大素数作为模数和基数。常用的组合是 base = 100007，mod = 2^63 - 1。
算法步骤：
- 二分搜索范围：[0, min(len(path) for path in paths)]
- 对于每个 mid，生成所有路径中长度为 mid 的子路径的哈希值
- 找到在所有路径中都出现的哈希值，如果存在则说明长度 mid 可行
- 使用滚动哈希优化子字符串哈希值的计算
时间复杂度优化：通过滚动哈希，每个长度的子路径哈希计算时间为 O(1)，总体效率较高。
代码实现
class Solution {
public:
int longestCommonSubpath(int n, vector<vector<int>>& paths) {
int left = 0, right = INT_MAX;
for (auto& path : paths) {
right = min(right, (int)path.size());
}
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (hasCommonSubpath(paths, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
private:
bool hasCommonSubpath(vector<vector<int>>& paths, int len) {
if (len == 0) return true;
long long base = 100007;
long long mod = (1LL << 63) - 1;
long long power = 1;
for (int i = 0; i < len - 1; i++) {
power = (power * base) % mod;
}
unordered_set<long long> common;
for (int i = 0; i < paths.size(); i++) {
unordered_set<long long> current;
long long hash = 0;
// Calculate hash for first window
for (int j = 0; j < len; j++) {
hash = (hash * base + paths[i][j]) % mod;
}
current.insert(hash);
// Rolling hash for remaining windows
for (int j = len; j < paths[i].size(); j++) {
hash = (hash - (paths[i][j - len] * power) % mod + mod) % mod;
hash = (hash * base + paths[i][j]) % mod;
current.insert(hash);
}
if (i == 0) {
common = current;
} else {
unordered_set<long long> temp;
for (long long h : current) {
if (common.count(h)) {
temp.insert(h);
}
}
common = temp;
if (common.empty()) return false;
}
}
return !common.empty();
}
};
class Solution:
def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:
def hasCommonSubpath(length):
if length == 0:
return True
base = 100007
mod = 2**63 - 1
power = pow(base, length - 1, mod)
common = None
for i, path in enumerate(paths):
if len(path) < length:
return False
current = set()
hash_val = 0
# Calculate hash for first window
for j in range(length):
hash_val = (hash_val * base + path[j]) % mod
current.add(hash_val)
# Rolling hash for remaining windows
for j in range(length, len(path)):
hash_val = (hash_val - path[j - length] * power) % mod
hash_val = (hash_val * base + path[j]) % mod
current.add(hash_val)
if i == 0:
common = current
else:
common &= current
if not common:
return False
return bool(common)
left, right = 0, min(len(path) for path in paths)
while left < right:
mid = (left + right + 1) // 2
if hasCommonSubpath(mid):
left = mid
else:
right = mid - 1
return left
public class Solution {
public int LongestCommonSubpath(int n, int[][] paths) {
int left = 0, right = int.MaxValue;
foreach (var path in paths) {
right = Math.Min(right, path.Length);
}
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (HasCommonSubpath(paths, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
private bool HasCommonSubpath(int[][] paths, int len) {
if (len == 0) return true;
long baseNum = 100007;
long mod = (1L << 63) - 1;
long power = 1;
for (int i = 0; i < len - 1; i++) {
power = (power * baseNum) % mod;
}
HashSet<long> common = null;
for (int i = 0; i < paths.Length; i++) {
if (paths[i].Length < len) return false;
var current = new HashSet<long>();
long hash = 0;
// Calculate hash for first window
for (int j = 0; j < len; j++) {
hash = (hash * baseNum + paths[i][j]) % mod;
}
current.Add(hash);
// Rolling hash for remaining windows
for (int j = len; j < paths[i].Length; j++) {
hash = (hash - (paths[i][j - len] * power) % mod + mod) % mod;
hash = (hash * baseNum + paths[i][j]) % mod;
current.Add(hash);
}
if (i == 0) {
common = current;
} else {
common.IntersectWith(current);
if (common.Count == 0) return false;
}
}
return common.Count > 0;
}
}
var longestCommonSubpath = function(n, paths) {
const m = paths.length;
const minLen = Math.min(...paths.map(p => p.length));
const base = 100001;
const mod = 2**53 - 1;
function getHash(path, start, len) {
let hash = 0;
let power = 1;
for (let i = 0; i < len; i++) {
hash = (hash + (path[start + i] * power) % mod) % mod;
if (i < len - 1) power = (power * base) % mod;
}
return hash;
}
function rollHash(oldHash, oldChar, newChar, power) {
let newHash = (oldHash - oldChar + mod) % mod;
newHash = (newHash / base) % mod;
newHash = (newHash + (newChar * power) % mod) % mod;
return newHash;
}
function hasCommonSubpath(len) {
if (len === 0) return true;
let power = 1;
for (let i = 0; i < len - 1; i++) {
power = (power * base) % mod;
}
const hashCounts = new Map();
for (let pathIdx = 0; pathIdx < m; pathIdx++) {
const path = paths[pathIdx];
if (path.length < len) return false;
const pathHashes = new Set();
let hash = getHash(path, 0, len);
pathHashes.add(hash);
for (let i = 1; i <= path.length - len; i++) {
hash = rollHash(hash, path[i - 1], path[i + len - 1], power);
pathHashes.add(hash);
}
if (pathIdx === 0) {
for (const h of pathHashes) {
hashCounts.set(h, 1);
}
} else {
const newHashCounts = new Map();
for (const h of pathHashes) {
if (hashCounts.has(h)) {
newHashCounts.set(h, hashCounts.get(h) + 1);
}
}
hashCounts.clear();
for (const [h, count] of newHashCounts) {
hashCounts.set(h, count);
}
}
}
for (const count of hashCounts.values()) {
if (count === m) return true;
}
return false;
}
let left = 0, right = minLen;
let result = 0;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (hasCommonSubpath(mid)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(S × log(min_len))，其中 S 是所有路径长度之和，min_len 是最短路径长度 |
| 空间复杂度 | O(S)，主要用于存储哈希值集合 |
相关题目
. Reconstruct Itinerary (Hard)