Maison > développement back-end > tutoriel php > Compression des cordes III

Compression des cordes III

Susan Sarandon
Libérer: 2024-11-05 07:08:02
original
528 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!

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