Permutation in String
Une permutation d’une chaîne utilise les mêmes lettres, dans n’importe quel ordre, chacune autant de fois que dans la chaîne d’origine : tar, rat et art sont des permutations les unes des autres. On vous donne deux chaînes s1 et s2 composées de lettres minuscules anglaises. Renvoyez true si une permutation de s1 apparaît dans s2 sous forme de sous-chaîne (une suite de caractères consécutifs), et false sinon.
Fonction
- s1string
- les lettres à réarranger
- s2string
- la chaîne dans laquelle effectuer la recherche
- Renvoieboolean
- vrai si une sous-chaîne de s2 est une permutation de s1
Contraintes
1 ≤ s1.length ≤ 2 × 1041 ≤ s2.length ≤ 5 × 104s1ets2ne contiennent que des lettres minuscules de l’alphabet anglais (aàz).s1peut être plus long ques2.
Exemples
- Entrée
- s1 = "tar"s2 = "smartphone"
- Sortie
- true
- Explication
- La sous-chaîne
artaux indices 2 à 4 desmartphonecontient una, unret unt, les mêmes lettres quetar.
- Entrée
- s1 = "noon"s2 = "onion"
- Sortie
- false
- Explication
- Les sous-chaînes de longueur 4 sont
onioetnion.noonnécessite deuxnet deuxo, et chaque fenêtre contient unià la place de l’une d’elles. Toutes les lettres denoonapparaissent dansonion, mais aucune fenêtre ne contient les bonnes quantités.
- Entrée
- s1 = "abcd"s2 = "dcb"
- Sortie
- false
- Explication
- Toute permutation de
abcdcomporte 4 lettres, etdcbn’en comporte que 3 : elle ne peut donc pas en contenir une.
+17 tests cachés à la soumission
Pour aller plus loin
Peux-tu renvoyer chaque indice de s2 où commence une permutation de s1, toujours en temps O(m + n) ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Dans une permutation, l’ordre des lettres n’a pas d’importance. Qu’est-ce qui détermine si une sous-chaîne de
s2est une permutation des1, et quelle doit être sa longueur ?Seules les sous-chaînes de longueur
m = s1.lengthpeuvent convenir, et une telle sous-chaîne est une permutation des1exactement lorsque ses 26 nombres d’occurrences des lettres sont égaux à ceux des1.Fais glisser une fenêtre de longueur
msurs2. À chaque étape, ajoute une lettre à droite et en retire une à gauche : mets donc à jour les compteurs de la fenêtre avec un +1 et un -1 au lieu de tout recompter, puis compare-les aux compteurs des1.
Solution
Énumérer les permutations de s1 est peine perdue : 10 lettres donnent déjà 3 628 800 ordres possibles. Pour s’en sortir, il faut cesser de se soucier de l’ordre. Une sous-chaîne de s2 est une permutation de s1 exactement lorsqu’elle a la même longueur m et le même nombre d’occurrences de chaque lettre. Chaque candidate est donc une fenêtre de longueur fixe, et tu peux faire glisser une fenêtre sur s2, en mettant à jour le nombre d’occurrences des lettres en ajoutant une lettre et en en retirant une à chaque étape.
Comptez chaque fenêtre depuis le début
Correcte, mais ne termine pas sur les plus gros tests
Intuition
La lecture littérale — construire toutes les permutations de s1 et les rechercher — échoue immédiatement : 20 lettres ont plus de 2 × 10^18 ordres possibles. Inverse plutôt la question. Une sous-chaîne de s2 est une permutation de s1 lorsqu’elle contient exactement m lettres et utilise chaque lettre autant de fois que s1. L’ordre des lettres n’a aucune importance.
Compte donc une fois les lettres de s1 dans un tableau de 26 nombres, avec l’indice 0 pour a et 25 pour z. Ensuite, prends chaque sous-chaîne de longueur m de s2, compte ses lettres dans un nouveau tableau et compare les deux tableaux. Pour tar dans smartphone, les fenêtres sont sma, mar, art, et ainsi de suite, et art correspond : un a, un r, un t.
Cette méthode est correcte, car elle examine chaque possibilité. Elle est lente parce que les fenêtres voisines partagent m-1 lettres et que tu les recomptes toutes. Avec m = 15,000 et n = 50,000, il y a 35,001 fenêtres de 15,000 lettres chacune, soit environ 5 × 10^8 étapes.
Algorithme
- Si
s1est plus long ques2, renvoiefalse. - Compte les lettres de
s1dans un tableauneedde 26 zéros. - Pour chaque indice de départ de 0 à
n-m, compte les lettres desmcaractères à partir de cet indice dans un nouveau tableau. - Si ce tableau est égal à
need, renvoietrue. - Après la dernière fenêtre, renvoie
false.
def checkInclusion(s1, s2):
m, n = len(s1), len(s2)
if m > n:
return False
need = [0] * 26 # need[0] is 'a', need[25] is 'z'
for ch in s1:
need[ord(ch) - 97] += 1
for start in range(n - m + 1):
# Count the letters of s2[start : start + m] from scratch
window = [0] * 26
for i in range(start, start + m):
window[ord(s2[i]) - 97] += 1
if window == need:
return True
return FalseFaites glisser la fenêtre et comparez 26 comptes
Intuition
Deux fenêtres voisines ne diffèrent que par deux lettres. Passer de mar à art enlève le m à gauche et ajoute le t à droite. Garde donc un seul tableau pour la fenêtre actuelle et modifie-le avec un +1 et un -1 à chaque étape, au lieu de compter à nouveau les lettres de m.
Remplis need à partir de s1 et window avec les m premières lettres de s2, puis compare-les. Ensuite, pour chaque i de m à n-1, ajoute s2[i], retire s2[i-m], puis compare à nouveau. La fenêtre est alors s2[i-m+1..i], toujours longue de m lettres.
Chaque étape coûte deux mises à jour et la comparaison de 26 nombres, quelle que soit la valeur de m. Pour l’entrée la plus grande, cela représente environ 26 × 50,000 = 1.3 × 10^6 opérations, soit un temps linéaire par rapport à la longueur de s2. C’est la solution que la plupart des personnes qui mènent des entretiens attendent.
Algorithme
- Si
s1est plus longue ques2, retournefalse. - Compte les caractères de
s1dansneedet lesmpremières lettres des2danswindow. - Si les deux tables sont égales, retourne
true. - Pour chaque
idemàn-1: ajoute 1 pours2[i], soustrais 1 pours2[i-m], et retournetruesi les tables sont égales. - Retourne
false.
def checkInclusion(s1, s2):
m, n = len(s1), len(s2)
if m > n:
return False
need = [0] * 26
window = [0] * 26
for i in range(m):
need[ord(s1[i]) - 97] += 1
window[ord(s2[i]) - 97] += 1 # the first window is s2[0 : m]
if window == need:
return True
for i in range(m, n):
window[ord(s2[i]) - 97] += 1 # s2[i] enters on the right
window[ord(s2[i - m]) - 97] -= 1 # s2[i - m] leaves on the left
if window == need:
return True
return FalseFaites glisser la fenêtre et suivez les lettres non équilibrées
Intuition
Comparer 26 nombres à chaque étape répète du travail, car une étape ne modifie que deux d’entre eux. Gardez plutôt un seul tableau balance : balance[c] indique le nombre d’occurrences de la lettre c dans s1, moins le nombre d’occurrences dans la fenêtre. La fenêtre est une permutation de s1 exactement lorsque les 26 soldes sont égaux à 0. À côté du tableau, gardez unbalanced, le nombre de lettres dont le solde n’est pas égal à 0, et renvoyez true dès qu’il atteint 0.
La mise à jour suit une seule règle. Avant de modifier balance[c], si sa valeur est 0, la lettre est sur le point de ne plus être équilibrée : ajoutez donc 1 à unbalanced. Après la modification, si sa valeur est 0, la lettre est équilibrée : soustrayez donc 1. Une lettre qui entre dans la fenêtre fait baisser son solde de 1 ; une lettre qui en sort le fait augmenter de 1. Un solde qui passe de 2 à 1 ne déclenche aucune des deux vérifications, ce qui est normal : la lettre était déséquilibrée et le reste.
Parcourez tar et smartphone. Au départ, les soldes sont les suivants : a : 1, r : 1, t : 1, donc unbalanced vaut 3. s et m entrent et le font passer à 5, puis a entre et ramène le solde de a à 0 : il passe à 4. r entre (3) tandis que s sort (2). t entre (1) tandis que m sort (0), et la fenêtre art est la réponse.
Vous pouvez tester unbalanced == 0 dès la toute première lettre. Tant que la fenêtre contient moins de m lettres, la somme des soldes est positive, donc au moins l’un d’eux n’est pas égal à 0. Chaque étape effectue une quantité fixe de travail : le parcours complet prend donc O(m + n), et le tableau contient toujours 26 nombres, ce qui représente un espace de O(1).
Algorithme
- Si
s1est plus long ques2, renvoiefalse. - Compte
s1dansbalanceet définisunbalancedcomme le nombre de lettres dont le solde est différent de 0. - Pour chaque indice
ides2, soustrais 1 au solde des2[i], en ajoutant 1 àunbalancedsi ce solde était égal à 0 et en soustrayant 1 s’il devient égal à 0. - Si
i ≥ m, ajoute 1 au solde des2[i-m]en appliquant le même suivi. - Si
unbalancedest égal à 0, renvoietrue. Après la boucle, renvoiefalse.
def checkInclusion(s1, s2):
m, n = len(s1), len(s2)
if m > n:
return False
# balance[c]: copies of letter c in s1 minus copies in the window
balance = [0] * 26
for ch in s1:
balance[ord(ch) - 97] += 1
unbalanced = sum(1 for b in balance if b != 0)
for i in range(n):
# s2[i] enters the window on the right
c = ord(s2[i]) - 97
if balance[c] == 0:
unbalanced += 1
balance[c] -= 1
if balance[c] == 0:
unbalanced -= 1
# s2[i - m] leaves on the left once the window would pass m letters
if i >= m:
c = ord(s2[i - m]) - 97
if balance[c] == 0:
unbalanced += 1
balance[c] += 1
if balance[c] == 0:
unbalanced -= 1
if unbalanced == 0:
return True
return False
Pièges et cas limites
La plupart des mauvaises réponses viennent des bords de la fenêtre, ou du fait de vérifier quelles lettres apparaissent au lieu de vérifier combien de fois elles apparaissent.
- Vérifier seulement que chaque lettre de
s1se trouve dans la fenêtre.oniocontient toutes les lettres denoon, mais ce n’est pas une permutation de celui-ci. Compare les fréquences. - Supprimer la mauvaise lettre. Lorsque
s2[i]entre, la lettre qui sort ests2[i-m], donc la fenêtre devients2[i-m+1..i]. Supprimers2[i-m+1]laisse une fenêtre dem-1lettres. - Ignorer la première fenêtre. Si tu compares seulement après avoir fait glisser la fenêtre, une permutation à l’index 0 ne sera jamais trouvée.
- Oublier le cas où
s1est plus long ques2. En Rust,n - mavec des longueurs non signées provoque un dépassement inférieur, et en Swift, la plage0...(n - m)provoque un plantage. Renvoie d’abordfalse. - Comparer des tableaux avec
==dans un langage où cela compare les références. En JavaScript et en Dart, deux tableaux différents ne sont jamais égaux avec==; en Java, utiliseArrays.equals.
Questions fréquentes4
Quelle est la complexité temporelle de Permutation in String ?
Avec une fenêtre glissante, la complexité est de O(m + n), où m est la longueur de s1 et n celle de s2. Tu comptes s1 une fois, puis chaque lettre de s2 entre une fois dans la fenêtre et en sort une fois. Recompter chaque fenêtre depuis le début coûte plutôt O(n · m).
La recherche d’une permutation dans une chaîne revient-elle à trouver un anagramme dans une chaîne ?
Oui. Une permutation de s1 est un anagramme de celui-ci ; la question est donc de savoir si une sous-chaîne de s2 de longueur m est un anagramme de s1. La vérification qu’il s’agit d’un anagramme entre deux chaînes entières compare une seule fois le nombre de lettres ; ici, la même comparaison est effectuée sur une fenêtre qui glisse le long de s2.
Pourquoi la fenêtre glissante a-t-elle une taille fixe ici ?
Chaque permutation de s1 contient exactement m lettres, donc seules les fenêtres de longueur m peuvent correspondre. Dans des problèmes comme celui de la plus longue sous-chaîne sans répétitions, la fenêtre s’agrandit et rétrécit ; ici, ses deux bords se déplacent ensemble, pas à pas.
Puis-je utiliser une table de hachage au lieu d’un tableau de 26 compteurs ?
Oui, et tu en as besoin si les chaînes peuvent contenir n’importe quel caractère. Avec uniquement des lettres minuscules, un tableau de 26 éléments est plus rapide et utilise un espace constant. Avec une map, supprime une clé lorsque son compteur tombe à 0 afin que deux maps contenant les mêmes lettres soient considérées comme égales, ou conserve le compteur unbalanced de l’approche précédente, qui fonctionne de la même manière avec une map.
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.
Python
def checkInclusion(s1, s2):
# Écrivez le code iciCas 1
Cas 2
Cas 3
Entrée
s1 = "tar" s2 = "smartphone"
Attendu
true