3163. Compression des cordes III
Difficulté :Moyen
Sujets : Chaîne
À partir d'un mot chaîne, compressez-le en utilisant l'algorithme suivant :
- Commencez avec une composition de chaîne vide. Tant que le mot n'est pas vide, utilisez l'opération suivante :
- Supprimer un préfixe de longueur maximale de mot composé d'un un seul caractèrec répétant au plus 9 fois.
- Ajoutez la longueur du préfixe suivi de c à comp.
Renvoyer la chaîne comp.
Exemple 1 :
-
Entrée : mot = "abcde"
-
Sortie : "1a1b1c1d1e"
-
Explication : Initialement, comp = "". Appliquez l'opération 5 fois, en choisissant "a", "b", "c", "d" et "e" comme préfixe dans chaque opération.
- Pour chaque préfixe, ajoutez "1" suivi du caractère à composer.
Exemple 2 :
-
Entrée : mot = "aaaaaaaaaaaaaabb"
-
Sortie : "9a5a2b"
-
Explication : Initialement, comp = "". Appliquez l'opération 3 fois en choisissant "aaaaaaaaa", "aaaaa" et "bb" comme préfixe dans chaque opération.
- Pour le préfixe "aaaaaaaaa", ajoutez "9" suivi de "a" à comp.
- Pour le préfixe "aaaaa", ajoutez "5" suivi de "a" à comp.
- Pour le préfixe « bb », ajoutez « 2 » suivi de « b » à comp.
Contraintes :
- 1 <= mot.longueur <= 2 * 105
-
le mot se compose uniquement de lettres anglaises minuscules.
Indice :
- À chaque fois, coupez simplement le même caractère dans le préfixe jusqu'à 9 fois maximum. Il est toujours préférable de couper un préfixe plus gros.
Solution :
Nous pouvons utiliser une approche gourmande pour compresser la chaîne en prenant le préfixe le plus long possible de caractères répétitifs (jusqu'à 9 occurrences à la fois), puis en ajoutant la longueur du préfixe avec le caractère au résultat.
Voici la solution étape par étape :
-
Initialiser les variables :
-
comp (la chaîne compressée) commence comme une chaîne vide.
- Utilisez un pointeur ou un index i pour suivre la position dans le mot.
-
Boucle à travers le mot :
- Bien qu'il reste des caractères dans le mot, recherchez le préfixe le plus long de caractères répétitifs qui ne dépasse pas 9 caractères.
- Comptez combien de fois le caractère actuel se répète consécutivement, jusqu'à un maximum de 9.
-
Ajouter à la chaîne compressée :
- Ajoutez le décompte suivi du caractère à comp.
- Déplacez le pointeur i vers l'avant du nombre de caractères traités.
-
Résultat du retour :
- Après avoir traité la chaîne entière, renvoyez la composition de chaîne compressée.
Implémentons cette solution en PHP : 3163. Compression des cordes III
Explication:
-
Boucle de comptage : Nous utilisons une boucle while à l'intérieur de la boucle principale pour compter les caractères consécutifs (jusqu'à 9) pour chaque caractère unique du mot.
-
Ajout des résultats : Après avoir compté chaque séquence, nous ajoutons le nombre et le caractère directement à la composition.
-
Mise à jour du pointeur : le pointeur de boucle principale i avance du nombre de caractères comptés, réduisant ainsi la taille de la chaîne restante à chaque itération.
Analyse de complexité
-
Complexité temporelle : O(n), où n est la longueur du mot. Chaque caractère est traité une fois.
-
Complexité spatiale : O(n) pour le résultat compressé stocké dans comp.
Cette solution est efficace et gère les cas extrêmes, tels que les séquences de moins de 9 caractères ou une seule occurrence de chaque caractère.
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 :
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!