C++深度优先搜索(DFS)算法的应用：树中可以形成回文的路径数

本文涉及知识点

深度优先搜索(DFS) 状态压缩

题目

给你一棵 树（即，一个连通、无向且无环的图），根 节点为 0 ，由编号从 0 到 n - 1 的 n 个节点组成。这棵树用一个长度为 n 、下标从 0 开始的数组 parent 表示，其中 parent[i] 为节点 i 的父节点，由于节点 0 为根节点，所以 parent[0] == -1 。

另给你一个长度为 n 的字符串 s ，其中 s[i] 是分配给 i 和 parent[i] 之间的边的字符。s[0] 可以忽略。

找出满足 u

如果一个字符串正着读和反着读都相同，那么这个字符串就是一个 回文 。

示例 1：

输入：parent = [-1,0,0,1,1,2], s = “acaabc”

输出：8

解释：符合题目要求的节点对分别是：

• (0,1)、(0,2)、(1,3)、(1,4) 和 (2,5) ，路径上只有一个字符，满足回文定义。
• (2,3)，路径上字符形成的字符串是 “aca” ，满足回文定义。
• (1,5)，路径上字符形成的字符串是 “cac” ，满足回文定义。
• (3,5)，路径上字符形成的字符串是 “acac” ，可以重排形成回文 “acca” 。

  示例 2：

  输入：parent = [-1,0,0,0,0], s = “aaaaa”

  输出：10

  解释：任何满足 u

  
  （图片来源网络，侵删）

  参数提示

  n == parent.length == s.length

  1 B的 字符数量的奇偶性相同。A->0可以拆分成A->C->0 ，0->B可以拆分成0->C->B。0到C和C到0抵消了。

  ###　时间复杂度

  o(27n)。n是节点数量,27是合法掩码的数量。

  代码

  class Solution{
  public:
  	long long countPalindromePaths(vector&parent, string s) {
  		m_c = parent.size();
  		m_str = s;
  		m_vNeiBo.assign(m_c, vector());
  		for (int i = 0; i