2416. Sum of Prefix Scores of Strings
Difficulty: Hard
Topics: Array, String, Trie, Counting
You are given an array words of size n consisting of non-empty strings.
We define the score of a string word as the number of strings words[i] such that word is a prefix of words[i].
Return an array answer of size n where answer[i] is the sum of scores of every non-empty prefix of words[i].
Note that a string is considered as a prefix of itself.
Example 1:
Example 2:
Constraints:
Hint:
Solution:
We can use a Trie data structure, which is particularly efficient for working with prefixes. Each node in the Trie will represent a letter of the words, and we'll maintain a counter at each node to store how many times that prefix has been encountered. This allows us to efficiently calculate the score of each prefix by counting how many words start with that prefix.
Insert Words into Trie:
Calculate Prefix Scores:
Build Answer Array:
Let's implement this solution in PHP: 2416. Sum of Prefix Scores of Strings
<?php class TrieNode { /** * @var array */ public $children; /** * @var int */ public $count; public function __construct() { $this->children = []; $this->count = 0; } } class Trie { /** * @var TrieNode */ private $root; public function __construct() { $this->root = new TrieNode(); } /** * Insert a word into the Trie and update the prefix counts * * @param $word * @return void */ public function insert($word) { ... ... ... /** * go to ./solution.php */ } /** * Get the sum of prefix scores for a given word * * @param $word * @return int */ public function getPrefixScores($word) { ... ... ... /** * go to ./solution.php */ } } /** * @param String[] $words * @return Integer[] */ function sumOfPrefixScores($words) { ... ... ... /** * go to ./solution.php */ } // Example usage: $words1 = ["abc", "ab", "bc", "b"]; $words2 = ["abcd"]; print_r(sumOfPrefixScores($words1)); // Output: [5, 4, 3, 2] print_r(sumOfPrefixScores($words2)); // Output: [4] ?> <h3> Explanation: </h3> <ol> <li> <p><strong>TrieNode Class:</strong></p> <ul> <li>Each node has an array of children (representing the next characters in the word) and a count to keep track of how many words share this prefix.</li> </ul> </li> <li> <p><strong>Trie Class:</strong></p> <ul> <li>The insert method adds a word to the Trie. As we insert each character, we increment the count at each node, representing how many words have this prefix.</li> <li>The getPrefixScores method calculates the sum of scores for all prefixes of a given word. It traverses through the Trie, adding up the count of each node corresponding to a character in the word.</li> </ul> </li> <li> <p><strong>Main Function (sumOfPrefixScores):</strong></p> <ul> <li>First, we insert all words into the Trie.</li> <li>Then, for each word, we calculate the sum of scores for its prefixes by querying the Trie and store the result in the result array.</li> </ul> </li> </ol> <h3> Example: </h3> <p>For words = ["abc", "ab", "bc", "b"], the output will be:<br> </p> <pre class="brush:php;toolbar:false">Array ( [0] => 5 [1] => 4 [2] => 3 [3] => 2 )
This approach ensures that we efficiently compute the prefix scores in linear time relative to the total number of characters in all words.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
The above is the detailed content of Sum of Prefix Scores of Strings. For more information, please follow other related articles on the PHP Chinese website!