Compter les chaînes de voyelles dans les plages

2559. Compter les chaînes de voyelles dans les plages

Difficulté :Moyen

Sujets : Tableau, chaîne, somme de préfixe

Vous recevez un tableau indexé à 0 de mots de chaînes et un tableau 2D de requêtes d'entiers.

Chaque requête requêtes[i] = [l_i, r_i] nous demande de trouver le nombre de chaînes présentes dans la plage l_i à r_i (tous deux inclus) de mots qui commencent et se terminent par une voyelle.

Renvoyer un tableau ans de taille requêtes.length, où ans[i] est la réponse à la i^ième requête.

Notez que les voyelles sont 'a', 'e', ​​'i', 'o' et 'u'.

Exemple 1 :

• Entrée : mots = ["aba","bcb","ece","aa","e"], requêtes = [[0,2],[1,4],[1, 1]]
• Sortie : [2,3,0]
• Explication : Les chaînes commençant et se terminant par une voyelle sont "aba", "ece", "aa" et "e".
  • La réponse à la requête [0,2] est 2 (chaînes "aba" et "ece").
  • pour interroger [1,4] est 3 (chaînes "ece", "aa", "e").
  • interroger [1,1] est 0.
  • On revient [2,3,0].

Exemple 2 :

• Saisie : mots = ["a","e","i"], requêtes = [[0,2],[0,1],[2,2]]
• Sortie : [3,2,1]
• Explication : Chaque chaîne satisfait aux conditions, nous retournons donc [3,2,1].

Contraintes :

• 1 5
• 1
• les mots [i] se composent uniquement de lettres anglaises minuscules.
• somme(mots[i].length) 5
• 1 5
• 0 i i

Indice :

1. Précalculez la somme des préfixes des chaînes qui commencent et se terminent par des voyelles.
2. Utilisez unordered_set pour stocker les voyelles.
3. Vérifiez si le premier et le dernier caractère de la chaîne sont présents dans le jeu de voyelles.
4. Soustrayez la somme des préfixes pour la plage [l-1, r] pour trouver le nombre de chaînes commençant et se terminant par des voyelles.

Solution :

Nous pouvons suivre ces étapes :

1. Vérifier les chaînes de voyelles : Créez une fonction d'assistance pour déterminer si une chaîne commence et se termine par une voyelle.
2. Précalculer les sommes des préfixes : Utilisez un tableau de somme de préfixes pour stocker le nombre cumulé de chaînes qui commencent et se terminent par des voyelles.
3. Réponses aux requêtes : Utilisez le tableau de somme de préfixes pour calculer efficacement le nombre de ces chaînes dans la plage spécifiée pour chaque requête.

Implémentons cette solution en PHP : 2559. Compter les chaînes de voyelles dans les plages

<?php /**
 * @param String[] $words
 * @param Integer[][] $queries
 * @return Integer[]
 */
function vowelStrings($words, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to check if a string starts and ends with a vowel
 *
 * @param $word
 * @return bool
 */
function isVowelString($word) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$words1 = ["aba", "bcb", "ece", "aa", "e"];
$queries1 = [[0, 2], [1, 4], [1, 1]];
print_r(countVowelStringsInRanges($words1, $queries1)); // Output: [2, 3, 0]

// Example 2
$words2 = ["a", "e", "i"];
$queries2 = [[0, 2], [0, 1], [2, 2]];
print_r(countVowelStringsInRanges($words2, $queries2)); // Output: [3, 2, 1]
?>

Explication:

1. Fonction isVowelString :

   • Vérifie si le premier et le dernier caractères de la chaîne sont des voyelles.
   • Utilise in_array pour déterminer si les caractères sont dans la liste prédéfinie de voyelles.

2. Tableau de somme de préfixes :

   • prefixSum[i] stocke le nombre cumulé de chaînes de voyelles jusqu'à l'index i-1.
   • Si le mot actuel satisfait à la condition, incrémentez le décompte.

3. Résolution des requêtes :

   • Pour une plage [l, r], le nombre de chaînes de voyelles est prefixSum[r 1] - prefixSum[l].

4. Efficacité :

   • La construction du tableau de somme de préfixes prend O(n), où n est le nombre de mots.
   • La résolution de chaque requête prend O(1), ce qui rend la complexité globale O(n q), où q est le nombre de requêtes.

Cas extrêmes :

• Toutes les chaînes commencent et se terminent par des voyelles.
• Aucune chaîne ne commence et ne se termine par des voyelles.
• Plages à un seul élément dans les requêtes.

Cette approche gère efficacement les contraintes du problème.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

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