Maison >développement back-end >tutoriel php >Somme des scores de préfixe des chaînes
2416. Somme des scores de préfixe des chaînes
Difficulté : Difficile
Sujets :Array, String, Trie, Counting
Vous recevez un tableau de mots de taille n composé de chaînes non vides.
Nous définissons le score d'un mot de chaîne comme le numéro de mots de chaîne[i] tel que ce mot est un préfixe de mots[i].
Renvoyer un tableau de réponse de taille n où réponse[i] est la somme des scores de chaque non vide préfixe de mots[i].
Notez qu'une chaîne est considérée comme un préfixe en soi.
Exemple 1 :
Exemple 2 :
Contraintes :
Indice :
Solution :
On peut utiliser une structure de données Trie, particulièrement efficace pour travailler avec des préfixes. Chaque nœud du Trie représentera une lettre des mots, et nous maintiendrons un compteur sur chaque nœud pour stocker le nombre de fois que ce préfixe a été rencontré. Cela nous permet de calculer efficacement le score de chaque préfixe en comptant combien de mots commencent par ce préfixe.
Insérer des mots dans Trie :
Calculer les scores de préfixe :
Créer un tableau de réponses :
Implémentons cette solution en PHP : 2416. Somme des scores de préfixe des chaînes
<?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> Explication: </h3> <ol> <li> <p><strong>Classe TrieNode :</strong></p> <ul> <li>Chaque nœud a un tableau d'enfants (représentant les caractères suivants dans le mot) et un décompte pour savoir combien de mots partagent ce préfixe.</li> </ul> </li> <li> <p><strong>Classe Trie :</strong></p> <ul> <li>La méthode insert ajoute un mot au Trie. Au fur et à mesure que nous insérons chaque caractère, nous incrémentons le nombre à chaque nœud, représentant le nombre de mots ayant ce préfixe.</li> <li>La méthode getPrefixScores calcule la somme des scores pour tous les préfixes d'un mot donné. Il parcourt le Trie, en additionnant le nombre de chaque nœud correspondant à un caractère du mot.</li> </ul> </li> <li> <p><strong>Fonction principale (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:
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!