Check if DFS Strings are Palindromes in Java

2025 年 5 月 12 日 | 阅读 9 分钟

可以使用图或树结构进行深度优先搜索 (DFS) 遍历，以检查沿路径累积的字符串是否构成回文。回文是指正反读起来都相同的序列。

应用 DFS 可以让我们构建字符串，检查每条路径，并使用字符串反转或双指针技术来确认字符串的对称性。这种方法对于涉及字母序列、单词图或树路径的问题尤其有效。

它适用于输入限制稍大的情况，因为其效率取决于深度和分支因子。通过及早消除非回文路径，剪枝等优化可以提高效率。

给定一个以节点 0 为根的树，包含 n 个节点，编号从 0 到 n - 1。一个大小为 n 的数组用于表示树，其中 parent[i] 是节点 i 的父节点。已知节点 0 是根，parent[0] == -1。此外，我们还提供了一个长度为 n 的字符串 s，其中分配给节点 i 的字符是 s[i]。

我们的任务是找到一个大小为 n 的布尔数组，如果生成的字符串 dfsStr 是回文，则返回 "true"；否则返回 false。

示例 1

输入

int parent[] = [-1, 0, 0, 0, 0]

String str = "aabcb"

输出：[true, true, true, true, true]

解释

parent 等于 [-1, 0, 0, 0, 0] 表示树的结构

根节点是节点 0（-1 表示没有父节点）。
节点 0 是节点 1、2、3 和 4 的直接父节点。
分配给每个节点的字符由 s = "aabcb" 表示。

要确定是否形成了回文，请从根节点到每个节点构建一个字符串

节点 0 → "a" → 回文 (true)
节点 1 → "aa" → 回文 (true)
节点 2 → "ab" → 回文 (true)
节点 3 → "ac" → 回文 (true)
节点 4 → "ab" → 回文 (true)

由于每条路径都形成回文，因此输出为 [true, true, true, true, true]。

示例 2

输入

int parent[] = [-1, 0, 0, 1, 1, 2],

String str = "aababa"

输出：[true, true, false, true, true, true]

解释

parent 等于 [-1, 0, 0, 1, 1, 2] 表示树的结构

根节点是节点 0（-1 表示没有父节点）。
节点 0 是节点 1 和 2 的父节点。
节点 1 是节点 3 和 4 的父节点。
节点 2 是节点 5 的父节点。

分配给每个节点的字符由 s = "aababa" 表示。

要确定是否形成了回文，请从根节点到每个节点构建一个字符串

节点 0 → "a" → 回文 (true)
节点 1 → "aa" → 回文 (true)
节点 2 → "ab" → 不是回文 (false)
节点 3 → "aaa" → 回文 (true)
节点 4 → "aab" → 回文 (true)
节点 5 → "aba" → 回文 (true)

由于节点 0、1、3、4 和 5 的路径是回文，但节点 2 不是，因此输出为 [true, true, false, true, true, true]。

方法：使用递归正向和反向哈希

使用滚动哈希和深度优先搜索 (DFS) 方法，提供的 Java 程序有效地确定树结构中的每个子树是否生成回文文本。

一个父数组，其中每个节点包含其子节点，用于构建树。在模运算中使用素数基 31 和模数 1,000,000,007 来提供快速且可靠的哈希计算。

为了使多项式哈希计算更有效，程序预先计算幂值。在 DFS 遍历期间，通过考虑子节点的哈希来计算每个节点的前向哈希和反向哈希。

回文是具有匹配的正向和反向哈希的子树字符串。该解决方案可以处理复杂的分层数据结构，因为它有效地处理大树而无需不必要的字符串操作。显示回文子树的布尔数组是程序的最终输出。

算法

步骤 1：声明常量 PRIME = 31（用于滚动哈希计算）和 MODULUS = 1,000,000,007（大素数以避免溢出）。

步骤 2：计算 powers[i] = (powers[i-1] * PRIME) 的百分比。为了进行有效的多项式哈希计算，请使用 MODULUS。

步骤 3：验证这是否只计算一次。

步骤 4：将输入字符串读取为字节数组，并将父数组。

步骤 5：初始化 child[][], LENGTH[], hash[], reverseHash[] 数组。

步骤 6：计算 childCount[] 以获取每个节点的子节点数。

步骤 7：从根节点 (0) 开始 DFS；对每个节点执行。

步骤 7.1：递归计算子节点的哈希。

步骤 7.2：计算正向哈希和反向哈希。

步骤 7.3：使用子树的整个字符串长度更新 LENGTH[node]。

步骤 8：通过从下往上遍历节点来识别回文子树。

步骤 8.1：如果 hash[i] == reverseHash[i]，则将 result[i] 标记为 true。

步骤 9：如果结果为 true，则以该节点为根的子树形成回文。返回 boolean[]。

实施

import java.io.*;
import java.lang.*;
import java.util.*;
public class DFSStringsPlaindrome 
{
    private final int PRIME = 31;
    private final int MODULUS = 1_000_000_007;
    private static int[] powers = new int[100_000 + 1];
    private int[][] child;
    private int[] LENGTH;
    private int[] hash;
    private int[] reverseHash;
    private byte[] s;
    public boolean[] findAnswer(int[] parent, String str) 
    {
        // For the first Submit or Run test case, 
        // only construct the powers table once.
        if (powers[0] == 0) 
        {
            powers[0] = 1;
            for (int i = 1; i < powers.length; i++)
            {
                powers[i] = (int)(((long)powers[i - 1] * PRIME) % MODULUS);
            }
        }
        // Initialize the class variables.
        final int n = parent.length;
        child = new int[n][];
        LENGTH = new int[n];
        hash = new int[n];
        reverseHash = new int[n];
        s = str.getBytes();
        // For every node, create a child link.
        // For every node, count the children.
        final int[] childCnt = new int[n];
        for (int i = 1; i < n; i++)
        {
            childCnt[parent[i]]++;
        }
        // For every node, allocate an array for children.
        for (int i = 0; i < n; i++) 
        {   
            child[i] = new int[childCnt[i]];
            childCnt[i] = 0;
        }
        // Complete the children links for every node.
        for (int i = 1; i < n; i++)     
        {
            child[parent[i]][childCnt[parent[i]]++] = i;
        }
        // To build tree information, use a depth-first search.
        dfs(0);
        boolean[] result = new boolean[n];
        for (int i = n - 1; i >= 0; i--)
        {
            if (hash[i] == reverseHash[i])
            {
                result[i] = true;
            }
        }
        return result;
    }
    private void dfs(int node) 
    {
        int current_Length = 0;
        int current_Hash = 0;
        int[] current_Children = child[node];
        // Determine the hash in the children's forward direction. 
        // Recurse to fill in the child information.
        for (int child : current_Children) 
        {
            dfs(child);
            current_Hash = (int)(((long)current_Hash * powers[LENGTH[child]] + hash[child]) % MODULUS);
            current_Length += LENGTH[child];
        }
        // Add a character from the current node to 
        // the end of "string" after children "strings".
        hash[node] = (int)(((long)current_Hash * PRIME + s[node]) % MODULUS);
        LENGTH[node] = ++current_Length;
        // Determine the hash in the opposite direction of the children.
        current_Hash = s[node];
        for (int i = current_Children.length - 1; i >= 0; i--) 
        {
            int child = current_Children[i];
            current_Hash = (int)(((long)current_Hash * powers[LENGTH[child]] + reverseHash[child]) % MODULUS);
        }
        reverseHash[node] = current_Hash;
    }
    public static void main(String[] args) 
    {
        int[] parent = {-1, 0, 0, 1, 1, 2};
        String str = "aababa";
        Solution solution = new Solution();
        boolean[] result = solution.findAnswer(parent, str);
        System.out.println(Arrays.toString(result));
    }
}   

输出

 
[true, true, false, true, true, true]

复杂度分析

上述代码的时间复杂度为 O(N)，其中 'N' 表示数组的长度，空间复杂度为 O(N)。

方法：使用 Manacher 算法

为了最大化回文子串的识别，此 Java 应用程序结合了基于邻接表的树表示、DFS 遍历和 Manacher 技术。它计算入出时间，存储节点访问顺序，并使用 DFS 有效地处理树节点。

借助 Manacher 方法（使用修改后的字符串格式围绕中心扩展），DFS 生成的字符串可以实现线性时间的回文测试。基于数组的索引可最大程度地减少不必要的计算并优化查找过程。

对于回文识别，该技术保证了 O(n) 的总时间复杂度，这使其非常高效。通过使用预计算的回文长度的逻辑条件来确定每个节点的子串有效性。

算法

步骤 1：创建一个 DFS 遍历字符串 (dfsString)，一个用于入场时间 (inT) 的数组，以及一个用于出场时间 (outT) 的数组。

步骤 2：在索引中维护 DFS 字符的跟踪。

步骤 3：为了表示树结构，请使用邻接列表 (arr_list)。

步骤 4：在 DFS 遍历中，准备 nodeString[][] 来存储每个节点的开始和结束索引。

步骤 5：使用 parent[] 数组进行迭代。

步骤 6：为了表示树，请填充邻接列表 (arr_list)。

步骤 7：从根节点 0 开始 DFS。

步骤 8：首次访问节点时，记录入场时间。

步骤 9：递归访问每个子节点。

步骤 10：处理完每个子节点后，保存出场时间。

步骤 11：按 DFS 顺序将节点字符附加到 dfsString[]。

步骤 12：为了实现一致的回文扩展，通过在字符之间插入 # 来转换 DFS 字符串。

步骤 13：初始化数组 p[] 以存储回文的长度。

步骤 14：扩展回文的中心并更新左右边界 (l) 和 (r)。

步骤 15：确定每个位置可能的最长回文长度。

步骤 16：使用 nodeString[][] 获取每个节点的子串索引。

步骤 17：计算子串的中心以及它之间的匹配回文边界。

步骤 18：确定回文是否比节点的子串长，并将结果记录为 true 或 false。

实施

import java.io.*;
import java.util.*;
public class ManacherDFSString 
{
    int[] inT;
    int[] outT;
    int time;
    // DFS traversal string is stored in a character array
    char[] dfsString;
    int index;
    // Array to hold the DFS traversal string's 
    // start and end indices for every node
    int[][] nodeString;
    // The tree's representation in an adjacency list
    ArrayList<Integer>[] arr_list;
    // How each node's answers are found
    public boolean[] findAnswer(int[] parent, String str) 
    {
        int length = str.length();
        arr_list = new ArrayList[length];
        boolean[] result = new boolean[length];
        nodeString = new int[length][2];
        dfsString = new char[length];
        inT = new int[length];
        outT = new int[length];
        // Initialize the adjacency list
        for (int i = 0; i < length; i++)
        {
            arr_list[i] = new ArrayList<>();
        }
        // Create the tree structure
        for (int i = 1; i < length; i++) 
        {
            arr_list[parent[i]].add(i);
        }
        // Perform the DFS traversal
        dfs(parent, str, 0);
        // Use Manacher's method to calculate palindrome lengths.
        int[] palin_length = countSubstrings(new String(dfsString));
        // Determine results using calculations of palindrome length.
        for (int i = 0; i < length; i++) 
        {
            int start = nodeString[i][0];
            int end = nodeString[i][1];
            int l = end - start + 1;
            int center = start + l / 2;
            int c1 = 2 * (center + 1) - 1;
            int c2 = 2 * (center + 1) - 2;
            end = 2 * (end + 1) - 1;
            if (l % 2 == 0)
            {
                result[i] = (end < c2 + palin_length[c2]);
            }
            else
            {
                result[i] = (end < c1 + palin_length[c1]);
            }
        }
        return result;
    }
    // Depth-First Search (DFS) traversal of the tree
    void dfs(int[] parent, String str, int node) 
    {
        inT[node] = time++;
        nodeString[node][0] = index;
        // Recursively traverse the child nodes
        for (int v : arr_list[node])
        {
            dfs(parent, str, v);
        }
        outT[node] = time++;
        nodeString[node][1] = index;
        // Using the DFS order, store the 
        // character from the input string.
        dfsString[index++] = str.charAt(node);
    }
    // Manacher's algorithm for determining the 
    // lengths of the longest palindromic substrings
    public int[] countSubstrings(String str) 
    {
        int n = str.length();
        StringBuilder str_build = new StringBuilder("$").append("#");
        // Use '#' to separate characters to achieve
        // consistent palindrome expansion.
        for (char c : str.toCharArray()) 
        {
            str_build.append(c).append("#");
        }
        str_build.append("^");
        n = str_build.length();
        int[] p = new int[n];
        int l = 1, r = 1;
        
        for (int i = 2; i < str_build.length() - 1; i++) 
        {
            p[i] = Math.max(0, Math.min(r - i, p[l + (r - i)]));
            // Expand around the center
            while (str_build.charAt(i - p[i]) == str_build.charAt(i + p[i])) 
            {
                p[i]++;
            }
            // Update the center and also the right boundary
            if (i + p[i] > r) 
            {
                l = i - p[i];
                r = i + p[i];
            }
        }
        return Arrays.copyOfRange(p, 1, p.length - 1);
    }
    public static void main(String[] args) 
    {
        int[] parent = {-1, 0, 0, 1, 1, 2}; 
        String str = "aababa"; 
        ManacherDFSString obj = new ManacherDFSString();
        boolean[] result = obj.findAnswer(parent, str);
        System.out.println(Arrays.toString(result));
    }
}   

输出

 
[true, true, false, true, true, true]

复杂度分析

上述代码的时间复杂度为 O(N)，其中 "N" 表示数组的长度，空间复杂度为 O(N)。

下一主题Java 中的序数

Check if DFS Strings are Palindromes in Java

方法：使用递归正向和反向哈希

算法

实施

复杂度分析

方法：使用 Manacher 算法

算法

实施

复杂度分析

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Check if DFS Strings are Palindromes in Java

方法：使用递归正向和反向哈希

算法

实施

复杂度分析

方法：使用 Manacher 算法

算法

实施

复杂度分析

相关帖子

Java 中的 Codility 传递汽车问题

Java 中的 Zumkeller 数

Java 中树的垂直锯齿形遍历

Multiply Two Strings in Java

如何在 Java 中更改日期中的天数

Java 如何将字节转换为十六进制

Java 中显示二叉树的奇数级别节点

Java Program to Swap Two Numbers Using Bitwise Operator

Java ART

Java Switch String

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器