相邻字符不同的最长路径
难度:
标签:
题目描述
给你一棵 树（即一个连通、无向、无环图），根节点是节点 0 ，这棵树由编号从 0 到 n - 1 的 n 个节点组成。用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树，其中 parent[i] 是节点 i 的父节点，由于节点 0 是根节点，所以 parent[0] == -1 。
另给你一个字符串 s ，长度也是 n ，其中 s[i] 表示分配给节点 i 的字符。
请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 ，并返回该路径的长度。
示例 1：
输入：parent = [-1,0,0,1,1,2], s = "abacbe" 输出：3 解释：任意一对相邻节点字符都不同的最长路径是：0 -> 1 -> 3 。该路径的长度是 3 ，所以返回 3 。 可以证明不存在满足上述条件且比 3 更长的路径。
示例 2：
输入：parent = [-1,0,0,0], s = "aabc" 输出：3 解释：任意一对相邻节点字符都不同的最长路径是：2 -> 0 -> 3 。该路径的长度为 3 ，所以返回 3 。
提示：
n == parent.length == s.length1 <= n <= 105- 对所有
i >= 1，0 <= parent[i] <= n - 1均成立 parent[0] == -1parent表示一棵有效的树s仅由小写英文字母组成
代码结果
运行时间: 420 ms, 内存: 59.2 MB
/*
* 思路：
* 使用 Java Stream 来构建邻接表并计算路径。
* 从根节点开始进行深度优先搜索（DFS），
* 计算每个节点的最长和次长路径长度。
*/
import java.util.*;
import java.util.stream.*;
public class SolutionStream {
private int maxLength = 0;
public int longestPath(int[] parent, String s) {
// 构建树的邻接表
List<List<Integer>> tree = IntStream.range(0, parent.length)
.mapToObj(i -> new ArrayList<Integer>())
.collect(Collectors.toList());
IntStream.range(1, parent.length).forEach(i -> tree.get(parent[i]).add(i));
// 从根节点开始DFS
dfs(tree, s, 0);
return maxLength;
}
private int dfs(List<List<Integer>> tree, String s, int node) {
int[] max = {0, 0};
for (int child : tree.get(node)) {
int length = dfs(tree, s, child);
if (s.charAt(node) != s.charAt(child)) {
if (length > max[0]) {
max[1] = max[0];
max[0] = length;
} else if (length > max[1]) {
max[1] = length;
}
}
}
maxLength = Math.max(maxLength, max[0] + max[1] + 1);
return max[0] + 1;
}
}
解释
方法:
此题解采用了深度优先搜索（DFS）结合动态规划（DP）的方式来处理问题。首先，将 parent 数组转换为邻接列表 dp，以便能够从任一节点遍历其子节点。对于每个节点，通过递归函数 func 检查其所有子节点，计算从当前节点向下可达的最长路径长度。关键点在于，我们需要同时维护两个长度：max_len（当前节点到子节点的最长不重复字符路径长度）和 sec_max_len（次长路径长度）。如果当前节点和子节点的字符不同，则更新这两个长度。最后，对于每个节点，其贡献的路径长度可能是 max_len + sec_max_len（即通过当前节点连接两个最长分支）。全局变量 ans 用于在所有节点中追踪最长的路径长度。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在构建邻接列表时，你是如何确保父节点在子节点前被处理的，这对算法的正确性有何影响？
▷🦆
对于递归函数func中的局部变量max_len和sec_max_len，为什么需要维护两个最大长度值而不是单一的最大长度值？
▷🦆
在计算最长路径时，为什么最终返回的结果需要将ans加一？
▷🦆
你提到如果当前节点和子节点字符不同，则可能会更新max_len和sec_max_len，那么如果字符相同，处理逻辑有何不同？
▷