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].

• Par exemple, si mots = ["a", "ab", "abc", "cab"], alors le score de "ab" est 2, puisque "ab" est un préfixe à la fois de "ab" et "abc".

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 :

• Saisie : mots = ["abc","ab","bc","b"]
• Sortie : [5,4,3,2]
• Explication : La réponse pour chaque chaîne est la suivante :
  • "abc" a 3 préfixes : "a", "ab" et "abc".
  • Il y a 2 chaînes avec le préfixe "a", 2 chaînes avec le préfixe "ab" et 1 chaîne avec le préfixe "abc".
  • Le total est la réponse[0] = 2 + 2 + 1 = 5.
  • "ab" a 2 préfixes : "a" et "ab".
  • Il y a 2 chaînes avec le préfixe "a" et 2 chaînes avec le préfixe "ab".
  • Le total est la réponse[1] = 2 + 2 = 4.
  • "bc" a 2 préfixes : "b" et "bc".
  • Il y a 2 chaînes avec le préfixe "b" et 1 chaîne avec le préfixe "bc".
  • Le total est la réponse[2] = 2 + 1 = 3.
  • "b" a 1 préfixe : "b".
  • Il y a 2 chaînes avec le préfixe "b".
  • Le total est la réponse[3] = 2.

Exemple 2 :

• Saisie : mots = ["abcd"]
• Sortie : [4]
• Explication :
  • "abcd" a 4 préfixes : "a", "ab", "abc" et "abcd".
  • Chaque préfixe a un score de un, donc le total est réponse[0] = 1 + 1 + 1 + 1 = 4.

Contraintes :

• 1
• 1
• les mots [i] sont constitués de lettres anglaises minuscules.

Indice :

1. Quelle structure de données vous permettra de suivre efficacement le score de chaque préfixe ?
2. Utilisez un Trie. Insérez-y tous les mots et conservez un compteur à chaque nœud qui vous indiquera combien de fois nous avons visité chaque préfixe.

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.

Approche:

1. Insérer des mots dans Trie :

   • Nous insérerons chaque mot dans le Trie caractère par caractère.
   • À chaque nœud (représentant un caractère), nous maintenons un compteur qui enregistre le nombre de mots passant par ce préfixe.

2. Calculer les scores de préfixe :

   • Pour chaque mot, au fur et à mesure que nous parcourons ses préfixes dans le Trie, nous additionnerons les compteurs stockés à chaque nœud pour calculer le score de chaque préfixe.

3. Créer un tableau de réponses :

   • Pour chaque mot, nous calculerons la somme des scores pour tous ses préfixes et la stockerons dans le tableau des résultats.

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]
?>

Explication:

1. Classe TrieNode :

   • 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.

2. Classe Trie :

   • 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.
   • 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.

3. Fonction principale (sumOfPrefixScores) :

   • First, we insert all words into the Trie.
   • 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.

Example:

For words = ["abc", "ab", "bc", "b"], the output will be:

Array
(
    [0] => 5
    [1] => 4
    [2] => 3
    [3] => 2
)

• "abc" has 3 prefixes: "a" (2 words), "ab" (2 words), "abc" (1 word) -> total = 5.
• "ab" has 2 prefixes: "a" (2 words), "ab" (2 words) -> total = 4.
• "bc" has 2 prefixes: "b" (2 words), "bc" (1 word) -> total = 3.
• "b" has 1 prefix: "b" (2 words) -> total = 2.

Time Complexity:

• Trie Construction: O(n * m) where n is the number of words and m is the average length of the words.
• Prefix Score Calculation: O(n * m) as we traverse each word's prefix in the Trie.

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:

• LinkedIn
• GitHub

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!