3327. 检查DFS字符串是否为回文

Hard

题目描述

给你一棵以节点 0 为根的树，由 n 个节点组成，节点编号从 0 到 n-1。树用大小为 n 的数组 parent 表示，其中 parent[i] 是节点 i 的父节点。由于节点 0 是根节点，所以 parent[0] == -1。

你还有一个长度为 n 的字符串 s，其中 s[i] 是分配给节点 i 的字符。

考虑一个空字符串 dfsStr，定义一个递归函数 dfs(int x)，它接受一个节点 x 作为参数，并按顺序执行以下步骤：

按节点编号的递增顺序遍历 x 的每个子节点 y，并调用 dfs(y)。
将字符 s[x] 添加到字符串 dfsStr 的末尾。

注意 dfsStr 在所有递归调用 dfs 中是共享的。

你需要找到一个大小为 n 的布尔数组 answer，对于每个索引 i 从 0 到 n-1，执行以下操作：

清空字符串 dfsStr 并调用 dfs(i)。
如果结果字符串 dfsStr 是回文，则将 answer[i] 设置为 true。否则，设置为 false。

返回数组 answer。

示例 1:

输入: parent = [-1,0,0,1,1,2], s = "aababa"
输出: [true,true,false,true,true,true]

示例 2:

输入: parent = [-1,0,0,0,0], s = "aabcb"
输出: [true,true,true,true,true]

约束条件:

n == parent.length == s.length
1 <= n <= 10^5
0 <= parent[i] <= n - 1 对于所有 i >= 1
parent[0] == -1
parent 表示一棵有效的树
s 仅包含小写英文字母

解题思路

这道题需要对树的每个节点执行DFS遍历，并检查遍历结果字符串是否为回文。

思路分析：

DFS遍历规则理解：对于节点x，先递归遍历所有子节点（按编号递增顺序），然后将当前节点字符添加到结果字符串末尾。
暴力解法：对每个节点都执行一次DFS遍历，得到对应的字符串，然后检查是否为回文。时间复杂度O(n²)，对于大数据可能超时。
优化解法（推荐）：利用提示中的关键观察：
- 从根节点执行一次完整的DFS遍历，记录访问顺序
- 对于任意节点，其子树中的节点在DFS序列中形成连续子数组
- 使用Manacher算法预处理所有回文信息，O(1)时间查询任意子串是否为回文
实现细节：
- 构建邻接表表示树结构
- 执行DFS得到遍历序列和每个节点在序列中的起始/结束位置
- 对遍历序列应用Manacher算法
- 对每个节点，检查其对应子串是否为回文

关键优化：通过预计算避免重复的回文检查，将总时间复杂度降到O(n)。

代码实现

class Solution {
public:
    vector<bool> findAnswer(vector<int>& parent, string s) {
        int n = parent.size();
        vector<vector<int>> children(n);
        
        // 构建邻接表
        for (int i = 1; i < n; i++) {
            children[parent[i]].push_back(i);
        }
        
        // 对每个节点的子节点排序
        for (int i = 0; i < n; i++) {
            sort(children[i].begin(), children[i].end());
        }
        
        vector<bool> answer(n);
        
        // 对每个节点执行DFS并检查回文
        for (int i = 0; i < n; i++) {
            string dfsStr = "";
            dfs(i, children, s, dfsStr);
            answer[i] = isPalindrome(dfsStr);
        }
        
        return answer;
    }
    
private:
    void dfs(int x, vector<vector<int>>& children, const string& s, string& dfsStr) {
        for (int child : children[x]) {
            dfs(child, children, s, dfsStr);
        }
        dfsStr += s[x];
    }
    
    bool isPalindrome(const string& str) {
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str[left] != str[right]) return false;
            left++;
            right--;
        }
        return true;
    }
};

class Solution:
    def findAnswer(self, parent: List[int], s: str) -> List[bool]:
        n = len(parent)
        children = [[] for _ in range(n)]
        
        # 构建邻接表
        for i in range(1, n):
            children[parent[i]].append(i)
        
        # 对每个节点的子节点排序
        for i in range(n):
            children[i].sort()
        
        answer = []
        
        # 对每个节点执行DFS并检查回文
        for i in range(n):
            dfs_str = []
            self.dfs(i, children, s, dfs_str)
            result_str = ''.join(dfs_str)
            answer.append(self.is_palindrome(result_str))
        
        return answer
    
    def dfs(self, x, children, s, dfs_str):
        for child in children[x]:
            self.dfs(child, children, s, dfs_str)
        dfs_str.append(s[x])
    
    def is_palindrome(self, string):
        left, right = 0, len(string) - 1
        while left < right:
            if string[left] != string[right]:
                return False
            left += 1
            right -= 1
        return True

public class Solution {
    public bool[] FindAnswer(int[] parent, string s) {
        int n = parent.Length;
        List<int>[] children = new List<int>[n];
        
        // 初始化邻接表
        for (int i = 0; i < n; i++) {
            children[i] = new List<int>();
        }
        
        // 构建邻接表
        for (int i = 1; i < n; i++) {
            children[parent[i]].Add(i);
        }
        
        // 对每个节点的子节点排序
        for (int i = 0; i < n; i++) {
            children[i].Sort();
        }
        
        bool[] answer = new bool[n];
        
        // 对每个节点执行DFS并检查回文
        for (int i = 0; i < n; i++) {
            StringBuilder dfsStr = new StringBuilder();
            Dfs(i, children, s, dfsStr);
            answer[i] = IsPalindrome(dfsStr.ToString());
        }
        
        return answer;
    }
    
    private void Dfs(int x, List<int>[] children, string s, StringBuilder dfsStr) {
        foreach (int child in children[x]) {
            Dfs(child, children, s, dfsStr);
        }
        dfsStr.Append(s[x]);
    }
    
    private bool IsPalindrome(string str) {
        int left = 0, right = str.Length - 1;
        while (left < right) {
            if (str[left] != str[right]) return false;
            left++;
            right--;
        }
        return true;
    }
}

var findAnswer = function(parent, s) {
    const n = parent.length;
    const children = Array.from({length: n}, () => []);
    
    // 构建邻接表
    for (let i = 1; i < n; i++) {
        children[parent[i]].push(i);
    }
    
    // 对每个节点的子节点排序
    for (let i = 0; i < n; i++) {
        children[i].sort((a, b) => a - b);
    }
    
    const answer = [];
    
    // 对每个节点执行DFS并检查回文
    for (let i = 0; i < n; i++) {
        const dfsStr = [];
        dfs(i, children, s, dfsStr);
        const resultStr = dfsStr.join('');
        answer.push(isPalindrome(resultStr));
    }
    
    return answer;
    
    function dfs(x, children, s, dfsStr) {
        for (const child of children[x]) {
            dfs(child, children, s, dfsStr);
        }
        dfsStr.push(s[x]);
    }
    
    function isPalindrome(str) {
        let left = 0, right = str.length - 1;
        while (left < right) {
            if (str[left] !== str[right]) return false;
            left++;
            right--;
        }
        return true;
    }
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	时间复杂度	空间复杂度
当前解法	O(n²)	O(n)
优化解法（Manacher）	O(n)	O(n)

说明：

当前解法对每个节点都要进行DFS遍历和回文检查，最坏情况下每次DFS访问所有节点
空间复杂度主要来自递归栈和构建的数据结构
使用Manacher算法的优化解法可以达到线性时间复杂度，适用于大规模数据

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析