3327. Check if DFS Strings Are Palindromes Hard

1/**
2 * [3327] Check if DFS Strings Are Palindromes
3 *
4 * 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.
5 * You are also given a string s of length n, where s[i] is the character assigned to node i.
6 * 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:
7 * 
8 * 	Iterate over each child y of x in increasing order of their numbers, and call dfs(y).
9 * 	Add the character s[x] to the end of the string dfsStr.
10 * 
11 * Note that dfsStr is shared across all recursive calls of dfs.
12 * 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:
13 * 
14 * 	Empty the string dfsStr and call dfs(i).
15 * 	If the resulting string dfsStr is a <span data-keyword="palindrome-string">palindrome</span>, then set answer[i] to true. Otherwise, set answer[i] to false.
16 * 
17 * Return the array answer.
18 *  
19 * <strong class="example">Example 1:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2024/09/01/tree1drawio.png" style="width: 240px; height: 256px;" />
21 * <div class="example-block">
22 * Input: <span class="example-io">parent = [-1,0,0,1,1,2], s = "aababa"</span>
23 * Output: <span class="example-io">[true,true,false,true,true,true]</span>
24 * Explanation:
25 * 
26 * 	Calling dfs(0) results in the string dfsStr = "abaaba", which is a palindrome.
27 * 	Calling dfs(1) results in the string dfsStr = "aba", which is a palindrome.
28 * 	Calling dfs(2) results in the string dfsStr = "ab", which is not a palindrome.
29 * 	Calling dfs(3) results in the string dfsStr = "a", which is a palindrome.
30 * 	Calling dfs(4) results in the string dfsStr = "b", which is a palindrome.
31 * 	Calling dfs(5) results in the string dfsStr = "a", which is a palindrome.
32 * </div>
33 * <strong class="example">Example 2:
34 * <img alt="" src="https://assets.leetcode.com/uploads/2024/09/01/tree2drawio-1.png" style="width: 260px; height: 167px;" />
35 * <div class="example-block">
36 * Input: <span class="example-io">parent = [-1,0,0,0,0], s = "aabcb"</span>
37 * Output: <span class="example-io">[true,true,true,true,true]</span>
38 * Explanation:
39 * Every call on dfs(x) results in a palindrome string.
40 * </div>
41 *  
42 * Constraints:
43 * 
44 * 	n == parent.length == s.length
45 * 	1 <= n <= 10^5
46 * 	0 <= parent[i] <= n - 1 for all i >= 1.
47 * 	parent[0] == -1
48 * 	parent represents a valid tree.
49 * 	s consists only of lowercase English letters.
50 * 
51 */
52pub struct Solution {}
53
54// problem: https://leetcode.com/problems/check-if-dfs-strings-are-palindromes/
55// discuss: https://leetcode.com/problems/check-if-dfs-strings-are-palindromes/discuss/?currentPage=1&orderBy=most_votes&query=
56
57// submission codes start here
58
59impl Solution {
60    pub fn find_answer(parent: Vec<i32>, s: String) -> Vec<bool> {
61        
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_3327() {
73    }
74}
75