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











PHP est un langage de script largement utilisé du côté du serveur, particulièrement adapté au développement Web. 1.Php peut intégrer HTML, traiter les demandes et réponses HTTP et prend en charge une variété de bases de données. 2.PHP est utilisé pour générer du contenu Web dynamique, des données de formulaire de traitement, des bases de données d'accès, etc., avec un support communautaire solide et des ressources open source. 3. PHP est une langue interprétée, et le processus d'exécution comprend l'analyse lexicale, l'analyse grammaticale, la compilation et l'exécution. 4.PHP peut être combiné avec MySQL pour les applications avancées telles que les systèmes d'enregistrement des utilisateurs. 5. Lors du débogage de PHP, vous pouvez utiliser des fonctions telles que error_reportting () et var_dump (). 6. Optimiser le code PHP pour utiliser les mécanismes de mise en cache, optimiser les requêtes de base de données et utiliser des fonctions intégrées. 7

Dans PHP, Password_Hash et Password_verify Les fonctions doivent être utilisées pour implémenter le hachage de mot de passe sécurisé, et MD5 ou SHA1 ne doit pas être utilisé. 1) Password_hash génère un hachage contenant des valeurs de sel pour améliorer la sécurité. 2) Password_verify Vérifiez le mot de passe et assurez-vous la sécurité en comparant les valeurs de hachage. 3) MD5 et SHA1 sont vulnérables et manquent de valeurs de sel, et ne conviennent pas à la sécurité de mot de passe moderne.

PHP et Python ont chacun leurs propres avantages et choisissent en fonction des exigences du projet. 1.Php convient au développement Web, en particulier pour le développement rapide et la maintenance des sites Web. 2. Python convient à la science des données, à l'apprentissage automatique et à l'intelligence artificielle, avec syntaxe concise et adaptée aux débutants.

PHP est largement utilisé dans le commerce électronique, les systèmes de gestion de contenu et le développement d'API. 1) E-commerce: Utilisé pour la fonction de panier et le traitement des paiements. 2) Système de gestion du contenu: utilisé pour la génération de contenu dynamique et la gestion des utilisateurs. 3) Développement des API: Utilisé pour le développement de l'API RESTful et la sécurité de l'API. Grâce à l'optimisation des performances et aux meilleures pratiques, l'efficacité et la maintenabilité des applications PHP sont améliorées.

Le type PHP invite à améliorer la qualité et la lisibilité du code. 1) Conseils de type scalaire: Depuis PHP7.0, les types de données de base sont autorisés à être spécifiés dans les paramètres de fonction, tels que INT, Float, etc. 2) Invite de type de retour: Assurez la cohérence du type de valeur de retour de fonction. 3) Invite de type d'union: Depuis PHP8.0, plusieurs types peuvent être spécifiés dans les paramètres de fonction ou les valeurs de retour. 4) Invite de type nullable: permet d'inclure des valeurs nulles et de gérer les fonctions qui peuvent renvoyer les valeurs nulles.

PHP est toujours dynamique et occupe toujours une position importante dans le domaine de la programmation moderne. 1) La simplicité de PHP et le soutien communautaire puissant le rendent largement utilisé dans le développement Web; 2) sa flexibilité et sa stabilité le rendent exceptionnelle dans la gestion des formulaires Web, des opérations de base de données et du traitement de fichiers; 3) PHP évolue et optimise constamment, adapté aux débutants et aux développeurs expérimentés.

PHP convient au développement Web, en particulier dans le développement rapide et le traitement du contenu dynamique, mais n'est pas bon dans les applications de la science des données et de l'entreprise. Par rapport à Python, PHP présente plus d'avantages dans le développement Web, mais n'est pas aussi bon que Python dans le domaine de la science des données; Par rapport à Java, PHP fonctionne moins bien dans les applications au niveau de l'entreprise, mais est plus flexible dans le développement Web; Par rapport à JavaScript, PHP est plus concis dans le développement back-end, mais n'est pas aussi bon que JavaScript dans le développement frontal.

PHP est principalement la programmation procédurale, mais prend également en charge la programmation orientée objet (POO); Python prend en charge une variété de paradigmes, y compris la POO, la programmation fonctionnelle et procédurale. PHP convient au développement Web, et Python convient à une variété d'applications telles que l'analyse des données et l'apprentissage automatique.
