diff options
author | Jack Sangdahl <[email protected]> | 2024-10-06 21:57:58 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-06 21:58:06 -0600 |
commit | b9c16a156eff8ebe6627a0869fdd6d360aec9bc5 (patch) | |
tree | a683212bc75ff3fba193586f76ad8a17d4772273 | |
parent | e4e9e626e5b5a9659510d4b71a742f14e4580079 (diff) | |
download | leetcode-b9c16a156eff8ebe6627a0869fdd6d360aec9bc5.tar.gz leetcode-b9c16a156eff8ebe6627a0869fdd6d360aec9bc5.zip |
2791. count paths that can form a palindrome in a tree
-rw-r--r-- | count_paths_form_palindrome_tree.c | 82 | ||||
-rw-r--r-- | count_paths_form_palindrome_tree.py | 39 |
2 files changed, 121 insertions, 0 deletions
diff --git a/count_paths_form_palindrome_tree.c b/count_paths_form_palindrome_tree.c new file mode 100644 index 0000000..07c8623 --- /dev/null +++ b/count_paths_form_palindrome_tree.c @@ -0,0 +1,82 @@ +// 2791. Count Paths That Can Form a Palindrome in a Tree +#include "leetcode.h" + +/* + * you are given a tree (ie. a connected, undirected graph that has no cycles) + * rooted at node 0 consisting of 'n' nodes numbered from 0 to 'n - 1'. the tree + * is represented by a 0-indexed array 'parent' of size 'n' where 'parent[i]' is + * the parent of node 'i'. since node 0 is the root, 'parent[0] == -1'. you are + * also given a string 's' of length 'n' where 's[i]' is the character assigned + * to the edge between 'i' and 'parent[i]'. 's[0]' can be ignored. return the + * number of pairs of nodes '(u, v)' such that 'u < v' and the characters + * assigned to edges on the path from 'u' to 'v' can rearranged to form a + * palindrome + */ + +void fill_table(int *parent, int parentSize, char *s, int *dp, int *filled, + int k, int *hash_table, int *hash_vals) { + if (filled[k]) + return; + if (!k) { + filled[k] = 1; + hash_table[0] = 1; + hash_vals[0] = 0; + return; + } + fill_table(parent, parentSize, s, dp, filled, parent[k], hash_table, + hash_vals); + int mask = dp[parent[k]] ^ (1 << (s[k] - 97)); + dp[k] = mask; + filled[k] = 1; + int kk = parentSize * 2, idx = mask % kk; + while (hash_vals[idx] != -1 && hash_vals[idx] != mask) { + idx++; + if (idx >= kk) + idx -= kk; + } + if (hash_vals[idx] == -1) + hash_vals[idx] = mask; + hash_table[idx]++; +} + +long long countPalindromePaths(int *parent, int parentSize, char *s) { + int kk = parentSize * 2, n = parentSize; + int *dp = (int *)calloc(n, sizeof(int)); + int *filled = (int *)calloc(n, sizeof(int)); + int *hash_table = (int *)calloc(kk, sizeof(int)); + int *hash_vals = (int *)malloc(kk * sizeof(int)); + for (int i = 0; i < kk; i++) + hash_vals[i] = -1; + for (int k = 0; k < n; k++) + fill_table(parent, parentSize, s, dp, filled, k, hash_table, hash_vals); + long long cnt = 0; + for (int k = 0; k < n; k++) { + int mask = dp[k]; + int idx = mask % kk; + while (hash_vals[idx] != -1 && hash_vals[idx] != mask) { + idx++; + if (idx >= kk) + idx -= kk; + } + cnt += hash_table[idx] - 1; + for (int j = 0; j < 26; j++) { + int new_mask = mask ^ (1 << j); + int new_idx = new_mask % kk; + while (hash_vals[new_idx] != -1 && hash_vals[new_idx] != new_mask) { + new_idx++; + if (new_idx >= kk) + new_idx -= kk; + } + cnt += hash_table[new_idx]; + } + } + free(dp), free(filled), free(hash_table), free(hash_vals); + return cnt; +} + +int main() { + int p1[] = {-1, 0, 0, 1, 1, 2}, p2[] = {-1, 0, 0, 0, 0}; + char *s1 = "acaabc", *s2 = "aaaaa"; + printf("%lld\n", countPalindromePaths(p1, ARRAY_SIZE(p1), s1)); // expect: 8 + printf("%lld\n", countPalindromePaths(p2, ARRAY_SIZE(p2), s2)); // expect: 10 +} diff --git a/count_paths_form_palindrome_tree.py b/count_paths_form_palindrome_tree.py new file mode 100644 index 0000000..e4740d8 --- /dev/null +++ b/count_paths_form_palindrome_tree.py @@ -0,0 +1,39 @@ +# 2791. Count Paths That Can Form a Palindrome in a Tree +from collections import Counter + +""" +you are given a tree (ie. a connected, undirected graph that has no cycles) +rooted at node 0 consisting of 'n' nodes numbered from 0 to 'n - 1'. the tree +is represented by a 0-indexed array 'parent' of size 'n' where 'parent[i]' is +the parent of node 'i'. since node 0 is the root, 'parent[0] == -1'. you are +also given a string 's' of length 'n' where 's[i]' is the character assigned +to the edge between 'i' and 'parent[i]'. 's[0]' can be ignored. return the +number of pairs of nodes '(u, v)' such that 'u < v' and the characters +assigned to edges on the path from 'u' to 'v' can rearranged to form a +palindrome +""" + + +class Solution(object): + def countPalindromePaths(self, parent, s): + """ + :type parent: List[int] + :type s: str + :rtype: int + """ + + def f(i): + return f(parent[i]) ^ (1 << (ord(s[i]) - ord("a"))) if i else 0 + + cnt, ans = Counter(), 0 + for i in range(len(parent)): + mask = f(i) + ans += cnt[mask] + sum(cnt[mask ^ (1 << j)] for j in range(26)) + cnt[mask] += 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.countPalindromePaths(parent=[-1, 0, 0, 1, 1, 2], s="acaabc")) + print(obj.countPalindromePaths(parent=[-1, 0, 0, 0, 0], s="aaaaa")) |