Jewels and Stones
Tu reçois deux chaînes de lettres. Chaque lettre de jewels désigne un type de bijou, et aucune lettre ne se répète. Chaque lettre de stones correspond à une pierre que tu possèdes. Retourne le nombre de tes pierres qui sont des bijoux. Les lettres sont sensibles à la casse : "a" et "A" sont deux types différents.
Fonction
- jewelsstring
- les types de pierres qui comptent comme des bijoux, une lettre pour chacun
- stonesstring
- les pierres que tu possèdes, une lettre chacune
- Renvoieinteger
- le nombre de pierres dont la lettre apparaît parmi les bijoux
Contraintes
1 ≤ jewels.length ≤ 521 ≤ stones.length ≤ 104- Les deux chaînes contiennent uniquement des lettres anglaises, minuscules et majuscules.
- Les lettres de
jewelssont toutes différentes.
Exemples
- Entrée
- jewels = "rR"stones = "rubyRRr"
- Sortie
- 4
- Explication
- Les types de pierres précieuses sont
retR. DansrubyRRr, les pierresr,R,Retrcorrespondent, tandis queu,betyne correspondent pas ; la réponse est donc4.
- Entrée
- jewels = "z"stones = "ZZZ"
- Sortie
- 0
- Explication
- Le seul type de joyau est
zen minuscule. Chaque pierre est unZmajuscule, d’un type différent, donc aucune ne compte.
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Pour une seule pierre, quelle question détermine si elle compte ?
Vous demandez « cette lettre est-elle une pierre précieuse ? » une fois par pierre. Quelle structure répond à cette question en temps constant ?
Mets les lettres de
jewelsdans un ensemble, puis parcoursstoneset compte chaque lettre contenue dans l’ensemble. Respecte la casse.
Solution
Pour chaque pierre, il te faut une réponse : cette lettre est-elle un joyau ? Rechercher chaque pierre dans la chaîne jewels répète la même analyse encore et encore. Place une fois les lettres des joyaux dans un ensemble, et chaque pierre se réduit à une seule recherche.
Scanne les joyaux pour chaque pierre
Intuition
Prenez les pierres une par une. Pour chaque pierre, parcourez jewels et arrêtez-vous à la première lettre qui lui correspond. Une correspondance ajoute 1 au compteur. Dans le premier exemple, la pierre u est comparée à r et R, ne trouve rien et n’ajoute rien.
Vous pouvez vous arrêter à la première correspondance, car les lettres des bijoux sont toutes différentes : une pierre peut donc correspondre à au plus une d’entre elles. Une pierre qui n’est pas un bijou doit être comparée à chaque lettre de bijou avant que vous puissiez le savoir.
Avec j types de bijoux et s pierres, cela représente jusqu’à j × s comparaisons. Ici, j ≤ 52, donc même 10^4 pierres nécessitent environ 5 × 10^5 comparaisons, et le parcours se termine à temps. Le gaspillage devient visible lorsque la liste des types s’allonge : la même recherche est répétée pour chaque pierre.
Algorithme
- Définis
countà0. - Pour chaque pierre, compare-la à chaque lettre de
jewels. - À la première lettre identique, ajoute
1àcountet passe à la pierre suivante. - Renvoie
count.
def numJewelsInStones(jewels, stones):
count = 0
for stone in stones:
for jewel in jewels:
if stone == jewel:
count += 1
break # the kinds are distinct: no second match is possible
return countPlace les bijoux dans un ensemble
Intuition
La question « cette lettre est-elle un joyau ? » a toujours la même réponse quand on la pose à propos de la même lettre. Réponds donc une seule fois par type : construis un ensemble à partir des lettres de jewels. Un ensemble vérifie l’appartenance en temps constant, donc chaque pierre ne nécessite qu’une recherche au lieu d’un parcours.
Pour le premier exemple, l’ensemble est {r, R}. En parcourant rubyRRr, les recherches répondent oui, non, non, non, oui, oui, oui : quatre joyaux. Construire l’ensemble prend j étapes et le parcours en prend s, donc le total est O(j + s).
L’ensemble contient au plus 52 lettres. Dans un langage sans ensemble intégré, un tableau de drapeaux indexé par le code du caractère fait le même travail.
Algorithme
- Construisez un ensemble contenant chaque lettre de
jewels. - Définissez
countà0. - Pour chaque pierre, ajoutez
1àcountsi l’ensemble la contient. - Retournez
count.
def numJewelsInStones(jewels, stones):
kinds = set(jewels)
count = 0
for stone in stones:
if stone in kinds:
count += 1
return count
Pièges et cas limites
L’algorithme consiste en une seule boucle. Les mauvaises réponses viennent de la façon dont les lettres sont comparées et comptées.
- Ne pas tenir compte de la casse. Mettre les deux chaînes en minuscules ferait correspondre
zetZ, et le deuxième exemple renverrait3au lieu de0. - Compter les types de bijoux distincts plutôt que les pierres.
rubyRRrcontient deux types de bijoux, mais quatre pierres précieuses ; chaque pierre compte, y compris les répétitions. - Construire l’ensemble à l’intérieur de la boucle sur les pierres. Le reconstruire pour chaque pierre coûte
jétapes à chaque fois et réintroduit leO(j × s)du parcours. Construis-le une fois, avant la boucle. - Inverser les arguments. L’ensemble doit contenir
jewels, et la boucle doit parcourirstones. Si les rôles sont inversés, le deuxième exemple compare le type de bijou uniquezaux pierres et renvoie toujours0, mais("a", "aaa")renvoie1au lieu de3.
Questions fréquentes3
Quelle est la complexité temporelle de Jewels and Stones ?
Avec un ensemble, c’est O(j + s) : j étapes pour créer l’ensemble à partir de jewels et une recherche en temps constant pour chacune des s pierres. Parcourir jewels pour chaque pierre est en O(j × s).
Pourquoi utiliser un ensemble de hachage pour Jewels and Stones ?
Chaque pierre pose le même type de question : sa lettre est-elle une pierre précieuse ? Un ensemble de hachage répond à cette question en temps constant, tandis que parcourir la chaîne jewels prend un temps proportionnel à sa longueur. Tu paies une fois pour construire l’ensemble et tu gagnes du temps pour chaque pierre ensuite.
Peux-tu le résoudre sans utiliser un ensemble ?
Oui. Les lettres sont des lettres anglaises, donc un tableau de 128 ou 256 indicateurs indexés par code de caractère fonctionne comme un ensemble sans aucun hachage. Marquez chaque lettre de bijou, puis comptez les pierres dont l’indicateur est activé. stones.count(jewels) en Ruby fait tout le travail en un seul appel, mais le tableau d’indicateurs montre ce qui se passe en dessous.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def numJewelsInStones(jewels, stones):
# Écrivez le code iciTest #1
Test #2
Arguments
jewels = "rR" stones = "rubyRRr"
Résultat attendu
4