Maison développement back-end tutoriel php Sous-séquences alindromiques de longueur uniques

Sous-séquences alindromiques de longueur uniques

Jan 05, 2025 am 01:16 AM

Unique Length-alindromic Subsequences

1930. Sous-séquences palindromiques uniques de longueur 3

Difficulté :Moyen

Sujets : Table de hachage, chaîne, manipulation de bits, somme de préfixes

Étant donné une chaîne s, renvoie le nombre de palindromes uniques de longueur trois qui sont une sous-séquence de s.

Notez que même s'il existe plusieurs façons d'obtenir la même sous-séquence, elle n'est toujours comptée qu'une seule fois.

Un palindrome est une chaîne qui lit la même chose vers l'avant et vers l'arrière.

Une sous-séquence d'une chaîne est une nouvelle chaîne générée à partir de la chaîne d'origine avec certains caractères (peut n'en être aucun) supprimés sans changer l'ordre relatif des caractères restants.

  • Par exemple, "ace" est une sous-séquence de "abcde".

Exemple 1 :

  • Entrée : s = "aabca"
  • Sortie : 3
  • Explication : Les 3 sous-séquences palindromiques de longueur 3 sont :
    • "aba" (sous-séquence de "aabca")
    • "aaa" (sous-séquence de "aabca")
    • "aca" (sous-séquence de "aabca")

Exemple 2 :

  • Entrée : s = "adc"
  • Sortie : 0
  • Explication : Il n'y a pas de sous-séquences palindromiques de longueur 3 dans "adc".

Exemple 3 :

  • Entrée : s = "bbcbaba"
  • Sortie : 4
  • Explication : Les 4 sous-séquences palindromiques de longueur 3 sont :
    • "bbb" (sous-séquence de "bbcbaba")
    • "bcb" (sous-séquence de "bbcbaba")
    • "bab" (sous-séquence de "bbcbaba")
    • "aba" (sous-séquence de "bbcbaba")

Contraintes :

  • 3 <= s.length <= 105
  • s se compose uniquement de lettres anglaises minuscules.

Indice :

  1. Quel est le nombre maximum de chaînes palindromiques de longueur 3 ?
  2. Comment pouvons-nous garder une trace des caractères apparus à gauche d'une position donnée ?

Solution :

Nous pouvons utiliser un algorithme efficace qui exploite le suivi des caractères de préfixe et de suffixe pour compter toutes les sous-séquences palindromiques valides.

Approche

  1. Piste des caractères de préfixe :
    Utilisez un tableau pour stocker l'ensemble de caractères rencontrés à gauche de chaque position dans la chaîne. Cela aidera à vérifier efficacement si un caractère peut former la première partie d'une sous-séquence palindromique.

  2. Piste des caractères de suffixe :
    Utilisez un autre tableau pour stocker l'ensemble de caractères rencontrés à droite de chaque position dans la chaîne. Cela aidera à vérifier efficacement si un personnage peut former la troisième partie d'une sous-séquence palindromique.

  3. Compter les sous-séquences palindromiques :
    Pour chaque caractère de la chaîne, considérez-le comme le caractère central d'un palindrome de longueur 3. Vérifiez toutes les combinaisons valides de caractères de préfixe et de suffixe pour déterminer des palindromes uniques.

  4. Résultats du magasin :
    Utilisez un jeu de hachage pour stocker des sous-séquences palindromiques uniques, en garantissant l'absence de doublons.

Implémentons cette solution en PHP : 1930. Sous-séquences palindromiques uniques de longueur 3






Explication:

  1. Tableau de préfixes :

    • Pour chaque caractère à la position i, le préfixe[i] stocke tous les caractères distincts rencontrés avant l'index i.
  2. Tableau de suffixes :

    • Pour chaque caractère en position i, le suffixe[i] stocke tous les caractères distincts rencontrés après l'index i.
  3. Caractère du milieu :

    • Considérez chaque personnage comme le milieu du palindrome. Pour chaque combinaison de caractères préfixe et suffixe qui correspond au caractère du milieu, formez un palindrome de longueur 3.
  4. Carte de hachage :

    • Utilisez un tableau associatif ($uniquePalindromes) pour stocker des palindromes uniques, en vous assurant que les doublons ne sont pas comptés.

Complexité

  • Complexité temporelle : O(n)

    • Parcourir la chaîne deux fois pour calculer les tableaux de préfixes et de suffixes.
    • Un troisième parcours vérifie les sous-séquences palindromiques valides.
  • Complexité spatiale : O(n)

    • Pour les tableaux de préfixes et de suffixes.

Sortir

Le code produit les résultats corrects pour les exemples donnés :

  • Entrée : "aabca" → Sortie : 3
  • Entrée : "adc" → Sortie : 0
  • Entrée : "bbcbaba" → Sortie : 4

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

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

Video Face Swap

Video Face Swap

Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Expliquez les jetons Web JSON (JWT) et leur cas d'utilisation dans les API PHP. Expliquez les jetons Web JSON (JWT) et leur cas d'utilisation dans les API PHP. Apr 05, 2025 am 12:04 AM

JWT est une norme ouverte basée sur JSON, utilisée pour transmettre en toute sécurité des informations entre les parties, principalement pour l'authentification de l'identité et l'échange d'informations. 1. JWT se compose de trois parties: en-tête, charge utile et signature. 2. Le principe de travail de JWT comprend trois étapes: la génération de JWT, la vérification de la charge utile JWT et l'analyse. 3. Lorsque vous utilisez JWT pour l'authentification en PHP, JWT peut être généré et vérifié, et les informations sur le rôle et l'autorisation des utilisateurs peuvent être incluses dans l'utilisation avancée. 4. Les erreurs courantes incluent une défaillance de vérification de signature, l'expiration des jetons et la charge utile surdimensionnée. Les compétences de débogage incluent l'utilisation des outils de débogage et de l'exploitation forestière. 5. L'optimisation des performances et les meilleures pratiques incluent l'utilisation des algorithmes de signature appropriés, la définition des périodes de validité raisonnablement,

Comment fonctionne le détournement de session et comment pouvez-vous l'atténuer en PHP? Comment fonctionne le détournement de session et comment pouvez-vous l'atténuer en PHP? Apr 06, 2025 am 12:02 AM

Le détournement de la session peut être réalisé via les étapes suivantes: 1. Obtenez l'ID de session, 2. Utilisez l'ID de session, 3. Gardez la session active. Les méthodes pour empêcher le détournement de la session en PHP incluent: 1. Utilisez la fonction Session_RegeReate_id () pour régénérer l'ID de session, 2. Stocker les données de session via la base de données, 3. Assurez-vous que toutes les données de session sont transmises via HTTPS.

Que sont les énumérations (enums) dans PHP 8.1? Que sont les énumérations (enums) dans PHP 8.1? Apr 03, 2025 am 12:05 AM

La fonction d'énumération dans PHP8.1 améliore la clarté et la sécurité du type du code en définissant les constantes nommées. 1) Les énumérations peuvent être des entiers, des chaînes ou des objets, améliorant la lisibilité du code et la sécurité des types. 2) L'énumération est basée sur la classe et prend en charge des fonctionnalités orientées objet telles que la traversée et la réflexion. 3) L'énumération peut être utilisée pour la comparaison et l'attribution pour assurer la sécurité du type. 4) L'énumération prend en charge l'ajout de méthodes pour implémenter une logique complexe. 5) La vérification stricte et la gestion des erreurs peuvent éviter les erreurs courantes. 6) L'énumération réduit la valeur magique et améliore la maintenabilité, mais prêtez attention à l'optimisation des performances.

Décrivez les principes solides et comment ils s'appliquent au développement de PHP. Décrivez les principes solides et comment ils s'appliquent au développement de PHP. Apr 03, 2025 am 12:04 AM

L'application du principe solide dans le développement de PHP comprend: 1. Principe de responsabilité unique (SRP): Chaque classe n'est responsable d'une seule fonction. 2. Principe ouvert et ferme (OCP): les changements sont réalisés par extension plutôt que par modification. 3. Principe de substitution de Lisch (LSP): les sous-classes peuvent remplacer les classes de base sans affecter la précision du programme. 4. Principe d'isolement d'interface (ISP): utilisez des interfaces à grain fin pour éviter les dépendances et les méthodes inutilisées. 5. Principe d'inversion de dépendance (DIP): les modules élevés et de bas niveau reposent sur l'abstraction et sont mis en œuvre par injection de dépendance.

Comment déboguer le mode CLI dans phpstorm? Comment déboguer le mode CLI dans phpstorm? Apr 01, 2025 pm 02:57 PM

Comment déboguer le mode CLI dans phpstorm? Lors du développement avec PHPStorm, nous devons parfois déboguer PHP en mode interface de ligne de commande (CLI) ...

Comment envoyer une demande post contenant des données JSON à l'aide de la bibliothèque Curl de PHP? Comment envoyer une demande post contenant des données JSON à l'aide de la bibliothèque Curl de PHP? Apr 01, 2025 pm 03:12 PM

Envoyant des données JSON à l'aide de la bibliothèque Curl de PHP dans le développement de PHP, il est souvent nécessaire d'interagir avec les API externes. L'une des façons courantes consiste à utiliser la bibliothèque Curl pour envoyer le post� ...

Expliquez la liaison statique tardive en PHP (statique: :). Expliquez la liaison statique tardive en PHP (statique: :). Apr 03, 2025 am 12:04 AM

Liaison statique (statique: :) ​​implémente la liaison statique tardive (LSB) dans PHP, permettant à des classes d'appel d'être référencées dans des contextes statiques plutôt que de définir des classes. 1) Le processus d'analyse est effectué au moment de l'exécution, 2) Recherchez la classe d'appel dans la relation de succession, 3) il peut apporter des frais généraux de performance.

See all articles