1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution:
def dfs(self, x: int, mask: int, s: str, con: List[List[int]], have: Dict[int, int]) -> int:
r: int = 0
if x:
mask ^= 1 << (ord(s[x]) - ord('a'))
i: int = 1 << 25
while i:
if mask ^ i in have:
r += have[mask ^ i]
i >>= 1
r += have.get(mask, 0)
have[mask] = have.get(mask, 0) + 1
for y in con[x]:
r += self.dfs(y, mask, s, con, have)
return r
def countPalindromePaths(self, parent: List[int], s: str) -> int:
n: int = len(s)
con: List[List[int]] = [[] for _ in range(n)]
for i in range(1, n):
con[parent[i]].append(i)
have: Dict[int, int] = {0: 1}
return self.dfs(0, 0, s, con, have)
|