Small & Simple Graph Count Traversal in Kotlin (Beats 100%)
\n\n# Intuition\nThe question that was asked; to sum up all the prefixes and occurences for every seperate word, can be achieved by simply counting how many tim
![image.png](https://assets.leetcode.com/users/images/385a22eb-35a2-4332-96e3-9a2e821e938a_1727262815.5776465.png)\n\n# Intuition\nThe question that was asked; to sum up all the prefixes and occurences for every seperate word, can be achieved by simply counting how many times a character reaches a node in a graph.\n\n# Approach\nBy letting every word traverse character for character from the same root, and keeping track of its traversal order, you could simply sum up the counts per node.\n![image.png](https://assets.leetcode.com/users/images/008ec8da-b219-4322-9868-55b6d52eeede_1727261688.4696357.png)\n\n```\ninput = ["abc", "abd"]\n"abc" = 0 + 2 + 2 + 1 = 5\n"abd" = 0 + 2 + 2 + 1 = 5\nresult = [5, 5]\n```\n\n- Create a root Node that every word will use as a start.\n- Traverse and build from the root, character per character\n   - Keep track of traversed nodes per word\n   - Increment a nodecounter every time it is visited by the algorithm\n- Afterwards, for every word, count up the nodecounters\n\n\n# Complexity\n- Time complexity:\n  - Building the graph: O(wordsCount * maxLengthOfWord) = O(n * m)\n  - Traversing the graph: O(wordsCount * maxLengtOfWord) = O(n * m)\n\n- Space complexity:\n    - Root node graph: O(wordscount * maxLengthOfWord) = O(n * m)\n    - Traversal List: O(wordscount * maxLengthOfWord) = O(n * m)\n\n\n# Code\n```kotlin []\nclass Solution {\n    fun sumPrefixScores(words: Array<String>): IntArray {\n        val root = Node()\n        fun traversal(word: String) = word.runningFold(root, Node::traverse)\n        return words\n            .map(::traversal)\n            .map { node -> node.sumOf(Node::count) }\n            .toIntArray()\n    }\n\n    private class Node {\n        val next = mutableMapOf<Char, Node>()\n        var count = 0\n        fun traverse(char: Char): Node = next.getOrPut(char, ::Node).apply { count++ }\n    }\n}\n```
['Trie', 'Kotlin']