Compression des cordes III

Susan Sarandon
Libérer: 2024-11-05 07:08:02
original
347 Les gens l'ont consulté

String Compression 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 * 105
  • 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!

source:dev.to
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Derniers articles par auteur
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!