LeetCode-2246. 相邻字符不同的最长路径【树 深度优先搜索 图 拓扑排序 数组 字符串】

本文主要是介绍LeetCode-2246. 相邻字符不同的最长路径【树 深度优先搜索 图 拓扑排序 数组 字符串】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

给你一棵 树（即一个连通、无向、无环图），根节点是节点 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.length
1 <= n <= 105
对所有 i >= 1 ，0 <= parent[i] <= n - 1 均成立
parent[0] == -1
parent 表示一棵有效的树
s 仅由小写英文字母组成

解题思路一：找路径

class Solution:def longestPath(self, parent: List[int], s: str) -> int:n = len(parent)g = [[] for _ in range(n)]for i in range(1, n):g[parent[i]].append(i)ans = 0def dfs(x: int) -> int:nonlocal ansmax_len = 0for y in g[x]:len = dfs(y) + 1if s[y] != s[x]:ans = max(ans, max_len + len)max_len = max(max_len, len)return max_lendfs(0)return ans + 1

时间复杂度：O(n)
空间复杂度：O(n)

背诵版：

同时解决：LeetCode-124. 二叉树中的最大路径和【树 深度优先搜索 动态规划 二叉树】
543. 二叉树的直径

class Solution:def longestPath(self, parent: List[int], s: str) -> int:n = len(parent)g = [[] for _ in range(n)]for i in range(1, n):g[parent[i]].append(i)ans = 0def dfs(x):nonlocal ansmax_len = 0for y in g[x]:len = dfs(y) + 1if s[y] != s[x]:ans = max(ans, max_len + len)max_len = max(max_len, len)return max_lendfs(0)return ans + 1

时间复杂度：O(n)
空间复杂度：O(n)

解题思路三：

时间复杂度：O(n)
空间复杂度：O(n)

---

创作不易，观众老爷们请留步… 动起可爱的小手，点个赞再走呗 (๑◕ܫ￩๑) 欢迎大家关注笔者，你的关注是我持续更博的最大动力

原创文章，转载告知，盗版必究

---

---

---

♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠

这篇关于LeetCode-2246. 相邻字符不同的最长路径【树 深度优先搜索 图 拓扑排序 数组 字符串】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---