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 了