Задача: 1519. Number of Nodes in the Sub-Tree With the Same Label
Сложность: medium

Вам дано дерево (т.е. связный неориентированный граф без циклов), состоящее из n узлов, пронумерованных от 0 до n - 1, и ровно n - 1 ребра. Корнем дерева является узел 0, и каждый узел дерева имеет метку, которая является строчной буквой, указанной в строке labels (т.е. узел с номером i имеет метку labels[i]).

Массив edges дан в форме edges[i] = [ai, bi], что означает, что существует ребро между узлами ai и bi в дереве.

Верните массив размера n, где ans[i] — это количество узлов в поддереве узла i, которые имеют ту же метку, что и узел i.

Поддерево дерева T — это дерево, состоящее из узла в T и всех его дочерних узлов.

Пример:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

👨‍💻 Алгоритм:

1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X.

2⃣Инициализируйте массив ans, хранящий ответ для каждого узла, и заполните его нулями.

3⃣Начните обход в глубину (DFS).

😎 Решение

class Solution {
    func dfs(_ node: Int, _ parent: Int, _ adj: [Int: [Int]], _ labels: [Character], _ ans: inout [Int]) -> [Int] {
        var nodeCounts = [Int](repeating: 0, count: 26)
        nodeCounts[Int(labels[node].asciiValue! - Character("a").asciiValue!)] = 1

        guard let children = adj[node] else {
            return nodeCounts
        }

        for child in children {
            if child == parent {
                continue
            }
            let childCounts = dfs(child, node, adj, labels, &ans)
            for i in 0..<26 {
                nodeCounts[i] += childCounts[i]
            }
        }

        ans[node] = nodeCounts[Int(labels[node].asciiValue! - Character("a").asciiValue!)]
        return nodeCounts
    }

    func countSubTrees(_ n: Int, _ edges: [[Int]], _ labels: String) -> [Int] {
        var adj = [Int: [Int]]()
        for edge in edges {
            adj[edge[0], default: []].append(edge[1])
            adj[edge[1], default: []].append(edge[0])
        }

        var ans = [Int](repeating: 0, count: n)
        let labelsArray = Array(labels)
        _ = dfs(0, -1, adj, labelsArray, &ans)
        return ans
    }
}

Ставь 👍 и забирай 📚 Базу знаний