2246. Longest Path With Different Adjacent Characters
给你一棵树 每个 node 都带有编号和一个字符
要你找出最长的 path 他的字符组成的字串中没有连续两个相同的字符
回传他的长度就好
Example 1:
https://assets.leetcode.com/uploads/2022/03/25/testingdrawio.png
Input: parent = [-1,0,0,1,1,2], s = "abacbe"
Output: 3
最长的是 0->1->3 = 'abc'
Example 2:
https://assets.leetcode.com/uploads/2022/03/25/graph2drawio.png
Input: parent = [-1,0,0,0], s = "aabc"
Output: 3
最长的是 3->0->2 或 2->0->3
思路:
1.可以想一下 path 是怎么组成的
在一条 path 中一定会有一个在这棵树中最高的 node 可能会是在 path 中间或顶点
然后从他的一个(如果是顶点)或两个(如果在中间) child node 往下连
如果对每个 node 我们都去找 以他为最高点的 path 最长是多少
这样检查完所有 node 就等于能检查所有可能的 path
2.至于要怎么知道以 node 为最高点的 path 长度
必须先算出他每个 child node 往下连的最长长度 然后从中挑两个最长的
同时这两个 child node 的字符不能和 node 的字符一样 这样才会合法
然后再把最长的那个和自己接起来 往上传给上一层用
3.所以 DFS 要做的事情有两件:
(1)找出以自己为最高点的最长path 用他去更新答案
(2)找出自己往下接最长能接多长 回传给上一层
Python code:
class Solution:
def longestPath(self, parent: List[int], s: str) -> int:
res = 1
children = defaultdict(list)
for i in range(1, len(parent)):
children[parent[i]].append(i)
def dfs(node):
nonlocal res
longest = 0
for child in children[node]:
path = dfs(child)
if s[child] != s[node]:
res = max(res, path + longest + 1)
longest = max(longest, path)
return longest + 1
dfs(0)
return res
解释比写扣还难==
感觉写好几天 DFS 了