Compression des cordes III

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 * 10⁵
• le mot se compose uniquement de lettres anglaises minuscules.

Indice :

1. À 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 :

1. 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.

2. 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.

3. 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.

4. 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 :


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!