. Sous-ensembles de mots

916. Sous-ensembles de mots

Difficulté :Moyen

Sujets : Tableau, table de hachage, chaîne

Vous recevez deux tableaux de chaînes mots1 et mots2.

Une chaîne b est un sous-ensemble de la chaîne a si chaque lettre de b apparaît dans une multiplicité inclusive.

• Par exemple, « wrr » est un sous-ensemble de « guerrier » mais n'est pas un sous-ensemble de « monde ».

Une chaîne a de mots1 est universelle si pour chaque chaîne b dans mots2, b est un sous-ensemble de a.

Renvoie un tableau de toutes les chaînes universelles dans mots1. Vous pouvez renvoyer la réponse dans n'importe quel ordre.

Exemple 1 :

• Saisie : mots1 = ["amazon","apple","facebook","google","leetcode"], mots2 = ["e","o"]
• Sortie : ["facebook","google","leetcode"]

Exemple 2 :

• Saisie : mots1 = ["amazon","apple","facebook","google","leetcode"], mots2 = ["l","e"]
• Sortie : ["apple","google","leetcode"]

Contraintes :

• 1 4
• 1
• les mots1[i] et les mots2[i] sont constitués uniquement de lettres anglaises minuscules.
• Toutes les chaînes de mots1 sont uniques.

Solution :

Nous devons identifier les mots de mots1 qui sont « universels », ce qui signifie que chaque chaîne de mots2 est un sous-ensemble du mot de mots1.

Approche:

1. Comptez la fréquence des caractères dans les mots2 :

   • Tout d'abord, nous devons déterminer le nombre maximum de chaque caractère dans toutes les chaînes de mots2. Cela nous donne le nombre d'occurrences requis pour que chaque caractère soit un sous-ensemble.

2. Vérifiez chaque mot dans les mots1 :

   • Pour chaque mot de mots1, comptez la fréquence de chaque caractère.
   • Si le nombre de caractères dans le mot des mots 1 atteint ou dépasse le nombre requis des mots 2, alors le mot est universel.

3. Renvoyez les mots universels :

   • Après avoir vérifié tous les mots dans mots1, renvoyez ceux qui sont universels.

Implémentons cette solution en PHP : 916. Sous-ensembles de mots

<?php /**
 * @param String[] $words1
 * @param String[] $words2
 * @return String[]
 */
function wordSubsets($words1, $words2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$words1 = ["amazon", "apple", "facebook", "google", "leetcode"];
$words2 = ["e", "o"];
print_r(wordSubsets($words1, $words2));  // Output: ["facebook", "google", "leetcode"]

$words2 = ["l", "e"];
print_r(wordSubsets($words1, $words2));  // Output: ["apple", "google", "leetcode"]
?>

Explication:

1. Création d'une carte de fréquence pour les mots2 : Nous parcourons chaque mot dans les mots2 et calculons la fréquence de chaque caractère. Nous gardons une trace de la fréquence maximale nécessaire pour chaque caractère dans tous les mots des mots2.

2. Vérification des mots1 Mots :Pour chaque mot des mots1, nous calculons la fréquence de chaque caractère et la comparons avec la fréquence requise des mots2. Si le mot répond aux exigences pour tous les caractères, il est considéré comme universel.

3. Résultat : Nous stockons tous les mots universels dans le tableau de résultats et le renvoyons à la fin.

Complexité temporelle :

• Construire la carte de fréquence pour les mots2 : O(n * m), où n est la longueur des mots2 et m est la longueur moyenne des mots dans les mots2.
• Vérification des mots1 : O(k * m), où k est la longueur des mots1 et m est la longueur moyenne des mots dans les mots1.
• La complexité temporelle totale est d'environ O(n * m k * m).

Cette approche garantit que nous vérifions chaque mot efficacement et répond aux 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!