Medium · Trie Visit Counts
Understand → Visualise → Practice.
A prefix score is how many words share it. Return the sum of all non-empty prefix scores for each word.
Insert all words into a trie, incrementing a counter at every node a word passes through. A word's score is the sum of the counters along its path.
For each word, increment the visit count of every node on its path.
Sum the counts of the nodes on the word's path.
One total per word, in input order.
O(total characters) time and space.
Comparing every pair of words is O(n² × length).
Read the full guide first: Tries and Prefix Search.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.