Check if DFS Strings Are Palindromes - Video Solutions
LeetCode ||Weekly Contest 420||Check if DFS Strings Are Palindromes||JAVA
Check if DFS Strings Are Palindromes - Video Solution
Watch 4 video solutions for Check if DFS Strings Are Palindromes, a hard level problem involving Array, Hash Table, String. This walkthrough by Samad Amir has 943 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- Iterate over each child
yofxin increasing order of their numbers, and calldfs(y). - Add the character
s[x]to the end of the stringdfsStr.
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:
- Empty the string
dfsStrand calldfs(i). - If the resulting string
dfsStris a palindrome, then setanswer[i]totrue. Otherwise, setanswer[i]tofalse.
Return the array answer.
Example 1:
Input: parent = [-1,0,0,1,1,2], s = "aababa"
Output: [true,true,false,true,true,true]
Explanation:
- Calling
dfs(0)results in the stringdfsStr = "abaaba", which is a palindrome. - Calling
dfs(1)results in the stringdfsStr = "aba", which is a palindrome. - Calling
dfs(2)results in the stringdfsStr = "ab", which is not a palindrome. - Calling
dfs(3)results in the stringdfsStr = "a", which is a palindrome. - Calling
dfs(4)results in the stringdfsStr = "b", which is a palindrome. - Calling
dfs(5)results in the stringdfsStr = "a", which is a palindrome.
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.length1 <= n <= 1050 <= parent[i] <= n - 1for alli >= 1.parent[0] == -1parentrepresents a valid tree.sconsists only of lowercase English letters.
Approach Overview
Problem Overview: You are given a rooted tree and a character assigned to each node. If you run a depth‑first search starting from any node and record the characters of nodes in its subtree in DFS order, you get a string. The task is to determine for every node whether this DFS string forms a palindrome.
The challenge is that subtree DFS strings can be large. Rebuilding the string for every node leads to repeated work. Efficient solutions reuse traversal order information and use hashing to check palindrome properties quickly.
Approach 1: DFS with Inline String Building (O(n²) time, O(n) space)
This straightforward approach performs a depth-first search starting from each node and constructs the DFS string for that subtree directly. During traversal, append the node's character to a temporary string or buffer. After the traversal finishes, check whether the resulting string is a palindrome using a two‑pointer scan from both ends.
The idea is simple but expensive. Many subtrees overlap, so the same nodes are visited repeatedly. If the tree is skewed, each DFS may traverse almost the entire structure. That pushes the total complexity to O(n²). This approach is mainly useful for understanding the problem or validating smaller inputs.
Approach 2: DFS with Adjacency List + Hashing (O(n) time, O(n) space)
The optimized method builds the tree using an adjacency list and performs a single DFS traversal. While traversing, record nodes in DFS order and compute rolling hashes for the generated sequence as well as its reverse. Subtree boundaries can be tracked using entry and exit indices during the DFS.
Once each subtree corresponds to a contiguous segment of the DFS order array, palindrome checks reduce to comparing forward and reverse hash values for that segment. Hash lookups are constant time using precomputed prefix hashes and powers. This avoids reconstructing strings entirely.
This solution combines tree traversal with a hash table style rolling hash technique. Because each node is processed once and each palindrome query is O(1), the overall complexity becomes linear.
Recommended for interviews: Start by explaining the brute force DFS string construction to demonstrate understanding of subtree traversal. Then move to the optimized hashing approach. Interviewers typically expect the single‑DFS solution because it eliminates repeated traversals and scales to large trees with O(n) processing.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Inline String Building | O(n²) | O(n) | Useful for understanding the problem or when constraints are small |
| DFS with Adjacency List + Rolling Hash | O(n) | O(n) | Best general solution for large trees and interview settings |