Compter le nombre de chaînes cohérentes

1684. Comptez le nombre de chaînes cohérentes

Difficulté :Facile

Sujets : Tableau, table de hachage, chaîne, manipulation de bits, comptage

Vous recevez une chaîne autorisée composée de caractères distincts et d'un tableau de chaînes de mots. Une chaîne est cohérente si tous les caractères de la chaîne apparaissent dans la chaîne autorisée.

Renvoyer le nombre de chaînes cohérentes dans le tableau mots.

Exemple 1 :

• Entrée : autorisée = "ab", mots = ["ad","bd","aaab","baa","badab"]
• Sortie : 2
• Explication : Les chaînes "aaab" et "baa" sont cohérentes puisqu'elles ne contiennent que les caractères 'a' et 'b'.

Exemple 2 :

• Entrée : autorisée = "abc", mots = ["a","b","c","ab","ac","bc","abc"]
• Sortie :7
• Explication : Toutes les chaînes sont cohérentes.

Exemple 3 :

• Entrée : autorisée = "cad", mots = ["cc","acd","b","ba","bac","bad","ac","d"]
• Sortie : 4
• Explication : Les chaînes "cc", "acd", "ac" et "d" sont cohérentes.

Contraintes :

• 1 <= mots.longueur <= 10⁴
• 1 <= autorisé.longueur <= 26
• 1 <= mots[i].length <= 10
• Les caractères autorisés sont distincts.
• les mots [i] et autorisés ne contiennent que des lettres anglaises minuscules.

Indice :

1. Une chaîne est incorrecte si elle contient un caractère non autorisé
2. Les contraintes sont suffisamment petites pour la force brute

Solution :

L'idée est de vérifier si chaque mot du tableau de mots est cohérent avec les caractères de la chaîne autorisée. Un mot est cohérent si tous ses caractères sont présents dans la chaîne autorisée.

Plan

1. Jeu de caractères autorisés :

   • Nous pouvons convertir la chaîne autorisée en un ensemble de caractères pour vérifier efficacement si chaque caractère du mot existe dans l'ensemble.

2. Vérification de la cohérence des mots :

   • Pour chaque mot du tableau de mots, vérifiez si tous ses caractères existent dans l'ensemble autorisé.

3. Compter les mots cohérents :

   • Initialiser un compteur. Pour chaque mot cohérent, incrémentez le compteur.

4. Renvoyer le décompte :

   • Une fois tous les mots traités, renvoie le nombre de mots cohérents.

Implémentons cette solution en PHP : 1684. Comptez le nombre de chaînes cohérentes

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

// Example usage:

// Example 1:
$allowed = "ab";
$words = ["ad", "bd", "aaab", "baa", "badab"];
echo countConsistentStrings($allowed, $words); // Output: 2

// Example 2:
$allowed = "abc";
$words = ["a","b","c","ab","ac","bc","abc"];
echo countConsistentStrings($allowed, $words); // Output: 7

// Example 3:
$allowed = "cad";
$words =  ["cc","acd","b","ba","bac","bad","ac","d"];
echo countConsistentStrings($allowed, $words); // Output: 4
?>




<h3>
  
  
  Explication:
</h3>

<ol>
<li>
<p><strong>Ensemble autorisé</strong> :</p>

<ul>
<li>Nous créons un tableau associatif $allowedSet où chaque clé est un caractère de la chaîne autorisée. Cela permet des recherches rapides.</li>
</ul>
</li>
<li>
<p><strong>Cohérence des mots</strong> :</p>

<ul>
<li>Pour chaque mot du tableau de mots, nous parcourons ses caractères et vérifions s'ils sont dans $allowedSet. Si nous trouvons un caractère qui ne figure pas dans l'ensemble, le mot est marqué comme incohérent et nous passons au mot suivant.</li>
</ul>
</li>
<li>
<p><strong>Comptage</strong> :</p>

<ul>
<li>Chaque fois que nous trouvons un mot cohérent, nous incrémentons le compteur $consistentCount.</li>
</ul>
</li>
<li>
<p><strong>Renvoyer le résultat</strong> :</p>

<ul>
<li>Après avoir traité tous les mots, le compteur contient le nombre de chaînes cohérentes, que nous renvoyons.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Complexité temporelle :
</h3>

<ul>
<li>
<strong>Complexité temporelle</strong> : O(n * m), où n est le nombre de mots et m est la longueur moyenne des mots. Nous parcourons tous les mots et leurs caractères.</li>
</ul>

<h3>
  
  
  Exemple de procédure pas à pas :
</h3>

<p>Pour la saisie :<br>
</p>

<pre class="brush:php;toolbar:false">$allowed = "ab";
$words = ["ad", "bd", "aaab", "baa", "badab"];

• Nous créons un ensemble : autoriséSet = ['a' => vrai, 'b' => vrai].
• Vérification de chaque mot :
  • "annonce" est incohérente (contient "d").
  • "bd" est incohérent (contient 'd').
  • "aaab" est cohérent (ne contient que "a" et "b").
  • "baa" est cohérent (ne contient que "a" et "b").
  • "badab" est incohérent (contient 'd').

Ainsi, la fonction renvoie 2.

Gestion des contraintes :

• Étant donné que les autorisations ne peuvent contenir que 26 caractères distincts et que les mots comportent au maximum 10 000 entrées, cette solution par force brute est suffisamment efficace compte tenu des contraintes. Chaque mot peut avoir une longueur maximale de 10, ce qui permet de parcourir tous les caractères.

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!