TheAlanWang

Notes

2791.Count Paths That Can Form a Palindrome in a Tree

6 min read

Question

Restate the problem

  • Given a rooted tree with n nodes, where parent[i] is the parent of node i
  • Each node i (except root) is associated with a character s[i]
  • A path between two nodes is valid if the characters along that path can be rearranged into a palindrome
  • Return the number of valid paths in the tree

Edge Case

  • All path letters are different
    • A path is valid only when at most one character has odd frequency.
MethodApproachTime ComplexitySpace Complexity
Method 1DFS + Prefix Parity State
Method 2 ⭐DFS + Bitmask

Method 1 - DFS + Prefix Parity State

DFS: 从根一路走到当前节点，维护当前路径状态
Use DFS with a racking odd/even character counts on the root-to-node path, and count previous states with the same mask or one-bit difference, because a path can form a palindrome iff at most one character has odd frequency.
沿着树做 DFS，记录根到当前节点路径上每个字符出现次数的奇偶性，并统计之前出现过的 相同状态或只差一位的状态，因为一条路径能重排成回文串 当且仅当至多一个字符出现奇数次。

理解1: 如何确认Path is a valid palindrome

  • 对于一条路径，只需要关心每个字符出现次数的 奇偶性
  • 用一个长度为 26 的 state 表示：
    • 0 = 偶数次 / 1 = 奇数次
  • 每经过一个字符，就把对应位置翻转一次
# 维护State
state = [0] * 26
 
# 遇到 a, state = [0,0,0,0,...]
idx = ord(char) - ord('a') # idx = 0
state[idx] = 1 - state[idx] # 1 - state[idx] = 1 - 0 = 1
# 再遇到 a。state = [1,0,0,0,...]
state[idx] = 1 - state[idx] # 1 - state[idx] = 1 - 1 = 0
 
# 如果一条路径最终满足：
if sum(state) <= 1:

理解2:
sum(state) <= 1 只能用于判断“某一条路径本身”是否合法；本题需要通过两个前缀状态的差来统计任意 ancestor → current 路径。

理解3: 通过新路径，计算 原路径一致或者仅差一位的路径

  • count里保存的访问过的路径 Eg. { (000..00): 1 }
  • 完全一致: ans += count[tuple(new_state)]
  • 差一位: 遍历all characters → 1-temp[k]

Approach

  • 先根据 parent 数组建树。
  • 用 DFS 从根节点开始遍历整棵树。
  • 维护一个长度为 26 的 state，表示当前 从根到当前节点路径上 每个字符出现次数的奇偶性：
    • 0 表示该字符出现了偶数次
    • 1 表示该字符出现了奇数次
  • 对于当前节点的每个子节点：
    • 先复制当前 state 得到 new_state
    • 根据 s[child] 找到对应字符下标
    • 将这一位翻转，表示路径上多经过了这个字符一次
  • 一条路径可以重排成回文，当且仅当：
    • 所有字符出现次数都是偶数，或者
    • 只有一个字符出现次数是奇数
  • 而两点之间路径的奇偶状态，可以由两个前缀状态的“差”来决定：
    • 如果两个前缀状态 完全相同，说明中间路径上所有字符都是偶数次
    • 如果两个前缀状态 恰好只差一位，说明中间路径上恰好只有一个字符是奇数次
  • 用hashmap count 记录：当前 DFS 路径上，每种前缀奇偶状态出现了多少次
  • 对于当前的 new_state：
    • 先加上 count[new_state]，表示统计“完全相同”的状态
    • 再枚举 26 个字符，把 new_state 的某一位翻转，统计所有“只差一位”的状态数量
  • 最后把当前 new_state 加入 count，继续向下 DFS。

Complexity

  • Time Complexity:
    • 每个节点会:
      • 查询 1 次完全相同状态
      • 枚举 26 个字符，查询 26 次只差一位的状态
  • Space Complexity:

Code

from collections import defaultdict
from typing import List
 
class Solution:
    def countPalindromePaths(self, parent: List[int], s: str) -> int:
        n = len(parent)
        tree = [[] for _ in range(n)]
        for i in range(1, n):
            tree[parent[i]].append(i)
 
        count = defaultdict(int)
        count[tuple([0] * 26)] = 1
        ans = 0
        def dfs(node, state):
            nonlocal ans
 
            for child in tree[node]:
                new_state = state[:]
 
                idx = ord(s[child]) - ord('a')
                new_state[idx] = 1 - new_state[idx]
 
                ans += count[tuple(new_state)]
 
                for k in range(26):
                    temp = new_state[:]
                    temp[k] = 1 - temp[k]
                    ans += count[tuple(temp)]
 
                count[tuple(new_state)] += 1
                dfs(child, new_state)
 
        dfs(0, [0] * 26)
        return ans

Method 2

Complexity

  • Time Complexity:
  • Space Complexity:

Code

from collections import defaultdict
from typing import List
 
class Solution:
    def countPalindromePaths(self, parent: List[int], s: str) -> int:
        n = len(parent)
        graph = [[] for _ in range(n)]
 
        for i in range(1, n):
            graph[parent[i]].append(i)
 
        count = defaultdict(int)
        count[0] = 1   # root prefix mask
        ans = 0
 
        def dfs(node: int, mask: int) -> None:
            nonlocal ans
 
            # edge parent[node] -> node has char s[node]
            mask ^= 1 << (ord(s[node]) - ord('a'))
 
            # same mask
            ans += count[mask]
 
            # differ by one bit
            for bit in range(26):
                ans += count[mask ^ (1 << bit)]
 
            count[mask] += 1
 
            for nei in graph[node]:
                dfs(nei, mask)
 
        for child in graph[0]:
            dfs(child, 0)
 
        return ans

Mistake

  • count[new_state] 表示统计“完全相同”的旧前缀状态

Graph View

Backlinks