Check if dfs strings are palindromes

Array Hash Table String Tree Depth-First Search Hash Function

20.1% acceptance

Feb 23, 2026

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 y of x in increasing order of their numbers, and call dfs(y). Add the character s[x] to the end of the string dfsStr. 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 dfsStr and call dfs(i). If the resulting string dfsStr is a palindrome, then set answer[i] to true. Otherwise, set answer[i] to false. Return the array answer.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn find_answer(parent: Vec<i32>, s: String) -> Vec<bool> {
    let n = parent.len();
    let chars: Vec<u8> = s.bytes().collect();
    let mut children: Vec<Vec<usize>> = vec![vec![]; n];
    for i in 1..n {
      children[parent[i] as usize].push(i);
    }
    // Sort children for consistency (already in order since parent[i] gives tree)
    for c in &mut children {
      c.sort_unstable();
    }
    
    // DFS to compute Euler tour (post-order)
    // dfs_string[in[x]..=out[x]] is the dfs string for subtree of x
    let mut dfs_str: Vec<u8> = Vec::with_capacity(n);
    let mut tin = vec![0usize; n];
    let mut tout = vec![0usize; n];
    
    // Iterative DFS post-order
    let mut stack: Vec<(usize, usize)> = vec![(0, 0)]; // (node, child_idx)
    while let Some((node, ci)) = stack.last_mut() {
      let node = *node;
      if *ci == 0 {
        tin[node] = dfs_str.len();
      }
      if *ci < children[node].len() {
        let child = children[node][*ci];
        *ci += 1;
        stack.push((child, 0));
      } else {
        dfs_str.push(chars[node]);
        tout[node] = dfs_str.len() - 1;
        stack.pop();
      }
    }
    
    // Now check if dfs_str[tin[i]..=tout[i]] is a palindrome using Manacher or hashing
    // Use polynomial hashing for O(n) palindrome checking
    // Eertree/Manacher on the full string then check each range
    
    // Z-function based approach:
    // For each node i, we need to check if dfs_str[tin[i]..=tout[i]] is a palindrome
    // Use hashing: compute prefix hashes and reverse hashes
    
    let m = dfs_str.len();
    let base: u64 = 131;
    let md: u64 = (1 << 61) - 1; // Mersenne prime
    
    let mul = |a: u64, b: u64| -> u64 {
      let r = (a as u128 * b as u128) % (md as u128);
      r as u64
    };
    let add = |a: u64, b: u64| -> u64 {
      let r = a + b;
      if r >= md { r - md } else { r }
    };
    
    let mut pw = vec![1u64; m + 1];
    for i in 1..=m {
      pw[i] = mul(pw[i-1], base);
    }
    
    let mut fwd = vec![0u64; m + 1];
    let mut rev = vec![0u64; m + 1];
    let dfs_rev: Vec<u8> = dfs_str.iter().cloned().rev().collect();
    
    for i in 0..m {
      fwd[i+1] = add(mul(fwd[i], base), dfs_str[i] as u64 + 1);
      rev[i+1] = add(mul(rev[i], base), dfs_rev[i] as u64 + 1);
    }
    
    let get_fwd = |l: usize, r: usize| -> u64 {
      // hash of dfs_str[l..=r]
      let h = fwd[r+1];
      let sub = mul(fwd[l], pw[r - l + 1]);
      if h >= sub { h - sub } else { h + md - sub }
    };
    let get_rev = |l: usize, r: usize| -> u64 {
      // hash of reverse of dfs_str[l..=r] = dfs_rev[m-1-r..=m-1-l]
      let rl = m - 1 - r;
      let rr = m - 1 - l;
      let h = rev[rr+1];
      let sub = mul(rev[rl], pw[rr - rl + 1]);
      if h >= sub { h - sub } else { h + md - sub }
    };
    
    (0..n).map(|i| {
      let l = tin[i];
      let r = tout[i];
      get_fwd(l, r) == get_rev(l, r)
    }).collect()
  }
}