Sous-séquences alindromiques de longueur uniques
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 :
- Quel est le nombre maximum de chaînes palindromiques de longueur 3 ?
- 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
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.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.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.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:
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.
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.
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.
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 :
- 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!

Outils d'IA chauds

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

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

Undress AI Tool
Images de déshabillage gratuites

Clothoff.io
Dissolvant de vêtements AI

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 !

Article chaud

Outils chauds

Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise
Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP

Dreamweaver CS6
Outils de développement Web visuel

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

Sujets chauds

Alipay Php ...

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,

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.

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.

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? Lors du développement avec PHPStorm, nous devons parfois déboguer PHP en mode interface de ligne de commande (CLI) ...

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

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.
