Hard
,Tree
,DFS
,Array
,String
,Graph
,Topological Sort
2246. Longest Path With Different Adjacent Characters
You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0
consisting of n
nodes numbered from 0
to n - 1
. The tree is represented by a 0-indexed array parent
of size n
, where parent[i]
is the parent of node i
. Since node 0
is the root, parent[0]
== -1.
You are also given a string s
of length n
, where s[i]
is the character assigned to node i
.
Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them.
Example 1:
Input: parent = [-1,0,0,1,1,2], s = "abacbe"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned.
It can be proven that there is no longer path that satisfies the conditions.
Example 2:
Input: parent = [-1,0,0,0], s = "aabc"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters is the path: 2 -> 0 -> 3. The length of this path is 3, so 3 is returned.
Constraints:
n
== parent.length
== s.length
n
<= 105parent[i]
<= n
- 1 for all i
>= 1parent[0]
== -1parent
represents a valid tree.s
consists of only lowercase English letters.
class Solution:
def longestPath(self, parent: List[int], s: str) -> int:
def dfs(node):
#print('#',node)
subtree_stats = []
ans = 1
max2 = [0,0]
for child in self.edge[node]:
if self.visited[child] == 1:
continue
self.visited[child] = 1
_ans = dfs(child)
if s[child] != s[node]:
if _ans > max2[0]:
#print('update1')
max2 = [_ans, max2[0]]
elif _ans > max2[1]:
max2[1] = _ans
#print(node,child, _ans , max2)
ans = sum(max2) + 1
#print(node, max2, ans)
self.ans[node] = ans
#print('#',node)
return max2[0]+1
n = len(s)
self.ans = [ 0 for _ in range(n)]
self.edge = dict()
for i in range(n):
self.edge[i] = []
for i, p in enumerate(parent):
if i == 0:
continue
self.edge[p].append(i)
self.visited = [ 0 for _ in range(n)]
self.visited[0]= 1
root_stat = dfs(0)
return max(self.ans)
玉山
提供一筆測資
S.longestPath([-1,0,0,1,1,2,3,3,3,4,5,5], "abacbeqwyyce"
class Solution:
def longestPath(self, parent: List[int], s: str) -> int:
tree = defaultdict(list)
for end, start in enumerate(parent):
tree[start].append(end)
ans = 1
def dfs(node):
nonlocal ans
max1, max2 = 0, 0
for child in tree[node]:
value = dfs(child)
if s[node] == s[child]: continue
if value > max1:
max1, max2 = value, max1
elif value > max2:
max2 = value
ans = max(ans, max1 + max2 + 1)
return max1 + 1
dfs(0)
return ans
Yen-Chi ChenSat, Jan 14, 2023