diff options
Diffstat (limited to 'longest_path_diff_adjacent_char.c')
-rw-r--r-- | longest_path_diff_adjacent_char.c | 74 |
1 files changed, 74 insertions, 0 deletions
diff --git a/longest_path_diff_adjacent_char.c b/longest_path_diff_adjacent_char.c new file mode 100644 index 0000000..e77ae15 --- /dev/null +++ b/longest_path_diff_adjacent_char.c @@ -0,0 +1,74 @@ +// 2246. Longest Path With Different Adjacent Characters +#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 node 'i'. return the legnth of the longest path in the + * tree such that no pair of adjacnet nodes on the path have the same character + * assigned to them. + */ + +struct node { + bool visited; + int children; + int *adjacent_list; +}; + +void dfs(int curr_node, int *dist, struct node **root, int parent_size, char *s, + int *res) { + int curr_child; + dist[curr_node] = 1; + root[curr_node]->visited = true; + for (int i = 0; i < root[curr_node]->children; i++) { + curr_child = root[curr_node]->adjacent_list[i]; + if (!root[curr_child]->visited) { + dfs(curr_child, dist, root, parent_size, s, res); + if (s[curr_node] != s[curr_child]) { + *res = fmax(*res, dist[curr_node] + dist[curr_child]); + dist[curr_node] = fmax(dist[curr_node], dist[curr_child] + 1); + } + } + } +} + +int longestPath(int *parent, int parentSize, char *s) { + int ans = 1; + int *cnt = (int *)calloc(parentSize, sizeof(int)); + int *dist = (int *)calloc(parentSize, sizeof(int)); + struct node **root = + (struct node **)malloc(parentSize * sizeof(struct node *)); + struct node *curr_node; + for (int i = 1; i < parentSize; i++) { + cnt[parent[i]]++; + cnt[i]++; + } + for (int i = 0; i < parentSize; i++) { + root[i] = (struct node *)malloc(sizeof(struct node)); + root[i]->visited = false; + root[i]->children = 0; + root[i]->adjacent_list = (int *)malloc(cnt[i] * sizeof(int)); + } + for (int i = 1; i < parentSize; i++) { + curr_node = root[parent[i]]; + curr_node->adjacent_list[curr_node->children] = i; + curr_node->children++; + } + dfs(0, dist, root, parentSize, s, &ans); + for (int i = 0; i < parentSize; i++) { + free(root[i]->adjacent_list); + free(root[i]); + } + free(cnt), free(dist), free(root); + return ans; +} + +int main() { + int p1[] = {-1, 0, 0, 1, 1, 2}, p2[] = {-1, 0, 0, 0}; + char *s1 = "abacbe", *s2 = "aabc"; + printf("%d\n", longestPath(p1, ARRAY_SIZE(p1), s1)); // expect: 3 + printf("%d\n", longestPath(p2, ARRAY_SIZE(p2), s2)); // expect: 3 +} |