We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if DFS Strings Are Palindromes

Number: 3603

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given a rooted tree with n nodes (indexed 0 to n-1) represented by an array parent where parent[0] == -1 and a lowercase English letter assigned to each node (given in string s), define dfs(x) as follows:

  1. For each child y of node x (processed in increasing order of node numbers), recursively call dfs(y).
  2. Append s[x] to a global string dfsStr. For every node i from 0 to n-1, clear dfsStr, call dfs(i), and determine if the resulting dfsStr is a palindrome. Return a boolean array answer where answer[i] is true if dfsStr is a palindrome for that call and false otherwise.

Key Insights

  • The DFS traversal is defined as a postorder traversal where the children are visited in sorted order and the node’s character is appended after processing its children.
  • The DFS string for any node i corresponds exactly to the concatenation of the DFS strings of its children (in increasing order) with the character s[i] appended.
  • Instead of constructing the whole DFS string (which may be very long), we can use a rolling hash (and its reverse) to check for the palindrome property in O(1) time per node.
  • The problem is solved with a postorder DP where for each node we compute: • H[node]: hash for the DFS string of the subtree rooted at node. • R[node]: hash for the reverse of the DFS string. • L[node]: length of the DFS string.
  • A node’s DFS string is a palindrome if and only if H[node] equals R[node].

Space and Time Complexity

Time Complexity: O(n log n) in the worst-case due to sorting children lists (in a star-shaped tree) and O(n) for the DFS postorder traversal. Space Complexity: O(n) for the tree, hash arrays, and recursion stack.

Solution

We perform a postorder depth-first search on the tree. For each node, we first process all its children (which are sorted in increasing order) to compute their DFS string hash (H) and reverse hash (R) as well as the length (L). The DFS string for a node i is defined as the concatenation of each child’s DFS string (in order) with the character at node i appended. We combine the children’s hashes using a rolling hash technique with a chosen base (e.g., 31) and a large modulus (e.g., 10^9 + 7) to keep numbers in range. Similarly, we compute the reverse hash by “prepending” the character at the node and then concatenating the reverse hashes of the children in reverse order. Finally, we compare H[i] and R[i] for each node. If they match, the DFS string is a palindrome. This bottom-up approach avoids constructing the potentially huge DFS strings explicitly.

Code Solutions

# Python solution with line-by-line comments

MOD = 10**9 + 7  # large prime modulus for hashing
BASE = 31        # base for polynomial rolling hash

def checkDFSStringsArePalindromes(parent, s):
    n = len(parent)
    # Build tree as an adjacency list; each node's children will be sorted
    tree = [[] for _ in range(n)]
    for i in range(1, n):
        tree[parent[i]].append(i)
    # sort children of each node to ensure increasing order
    for children in tree:
        children.sort()
    
    # Arrays to store forward hash, reverse hash, and length of the DFS string for each node.
    H = [0] * n  # forward hash of DFS string for subtree rooted at node
    R = [0] * n  # reverse hash of DFS string (i.e., hash of the reversed DFS string)
    L = [0] * n  # length of DFS string for subtree rooted at node
    
    # Pre-calculate powers of BASE up to n to avoid recomputation.
    maxLen = n  # maximum possible string length is n in worst-case chain.
    power = [1] * (maxLen + 1)
    for i in range(1, maxLen + 1):
        power[i] = (power[i-1] * BASE) % MOD

    # Postorder DFS to compute H[node], R[node] and L[node]
    def dfs(node):
        # Initialize res for forward hash and set total length to 0.
        forwardHash = 0
        totalLength = 0
        # Process each child in sorted increasing order.
        for child in tree[node]:
            dfs(child)
            # Combine the child’s hash to forwardHash
            forwardHash = (forwardHash * power[L[child]] + H[child]) % MOD
            totalLength += L[child]
        # Append the current node's character to the end of the DFS string.
        ch_val = ord(s[node]) - ord('a') + 1
        H[node] = (forwardHash * BASE + ch_val) % MOD
        L[node] = totalLength + 1  # Add one for the current node
        
        # Now compute reverse hash for the reversed DFS string.
        # For reversed DFS string, the character at node comes first.
        reverseHash = ch_val  # start with the character at node.
        # Then, process the children in reverse order.
        for child in reversed(tree[node]):
            reverseHash = (reverseHash * power[L[child]] + R[child]) % MOD
        R[node] = reverseHash
    
    # Compute hashes for every node using DFS starting from the root (or every node for full tree DP)
    # Since the tree is valid and connected, a single DFS from 0 will compute for all nodes.
    dfs(0)
    
    # Build the answer: for every node, check if its DFS string is a palindrome.
    answer = [False] * n
    for i in range(n):
        answer[i] = (H[i] == R[i])
    return answer

# Example usage:
if __name__ == "__main__":
    parent = [-1,0,0,1,1,2]
    s = "aababa"
    print(checkDFSStringsArePalindromes(parent, s))  # Expected: [True, True, False, True, True, True]
← Back to All Questions