Check if DFS Strings Are Palindromes - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
3327. Check if DFS Strings Are Palindromes
Hard
50 Points
Array
Hash Table
String
Tree
Depth-First Search
Hash Function
You are given a tree rooted at node 0, consisting of n nodes numbered from 0 to n - 1. The tree is represented by an 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.
Consider an empty string dfsStr, and define a recursive function dfs(int x) that takes a node x as a parameter and performs the following steps in order:
Note that dfsStr is shared across all recursive calls of dfs.
You need to find a boolean array answer of size n, where for each index i from 0 to n - 1, you do the following:
Return the array answer.
Examples
Example 1
Input: parent = [-1,0,0,1,1,2], s = "aababa"
Output: [true,true,false,true,true,true]
Explanation:
Example 2
Input: parent = [-1,0,0,0,0], s = "aabcb"
Output: [true,true,true,true,true]
Explanation:
Every call on dfs(x) results in a palindrome string.
Constraints
n == parent.length == s.length
1 <= n <= 105
0 <= parent[i] <= n - 1 for all i >= 1.
parent[0] == -1
parent represents a valid tree.
s consists only of lowercase English letters.
3327. Check if DFS Strings Are Palindromes
Hard
50 Points
Array
Hash Table
String
Tree
Depth-First Search
Hash Function
You are given a tree rooted at node 0, consisting of n nodes numbered from 0 to n - 1. The tree is represented by an 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.
Consider an empty string dfsStr, and define a recursive function dfs(int x) that takes a node x as a parameter and performs the following steps in order:
Note that dfsStr is shared across all recursive calls of dfs.
You need to find a boolean array answer of size n, where for each index i from 0 to n - 1, you do the following:
Return the array answer.
Examples
Example 1
Input: parent = [-1,0,0,1,1,2], s = "aababa"
Output: [true,true,false,true,true,true]
Explanation:
Example 2
Input: parent = [-1,0,0,0,0], s = "aabcb"
Output: [true,true,true,true,true]
Explanation:
Every call on dfs(x) results in a palindrome string.