Diviser une chaîne en nombre maximum de sous-chaînes uniques

1593. Diviser une chaîne en nombre maximum de sous-chaînes uniques

Difficulté :Moyen

Sujets : Table de hachage, chaîne, retour en arrière

Étant donné une chaîne s, renvoie le nombre maximum de sous-chaînes uniques en lesquelles la chaîne donnée peut être divisée.

Vous pouvez diviser les chaînes en n'importe quelle liste de sous-chaînes non vides, où la concaténation des sous-chaînes forme la chaîne d'origine. Cependant, vous devez diviser les sous-chaînes de telle sorte qu'elles soient toutes uniques.

Une sous-chaîne est une séquence contiguë de caractères dans une chaîne.

Exemple 1 :

• Entrée : s = "ababccc"
• Sortie : 5
• Explication : Une façon de diviser au maximum est ['a', 'b', 'ab', 'c', 'cc']. Le fractionnement comme ['a', 'b', 'a', 'b', 'c', 'cc'] n'est pas valide car vous avez 'a' et 'b' plusieurs fois.

Exemple 2 :

• Entrée : s = "aba"
• Sortie : 2
• Explication : Une façon de diviser au maximum est ['a', 'ba'].

Exemple 3 :

• Entrée : s = "aa"
• Sortie : 1
• Explication : Il est impossible de diviser davantage la chaîne.

Contraintes :

• 1 <= s.length <= 16
• s ne contient que des lettres anglaises minuscules.

Indice :

1. Utilisez un ensemble pour savoir quelles sous-chaînes ont déjà été utilisées
2. Essayez chaque sous-chaîne possible à chaque position et revenez en arrière si une division complète n'est pas possible

Solution :

Nous pouvons utiliser une approche de retour en arrière. Cela implique d'essayer de manière récursive de créer des sous-chaînes à partir de la position actuelle dans la chaîne et de garder une trace des sous-chaînes uniques que nous avons utilisées jusqu'à présent.

Voici une solution étape par étape :

1. Fonction récursive : Créez une fonction qui explorera toutes les sous-chaînes possibles à partir de l'index actuel de la chaîne.
2. Définir pour l'unicité : utilisez un ensemble (ou un tableau en PHP) pour garder une trace des sous-chaînes uniques qui ont été utilisées dans le chemin de récursion actuel.
3. Backtracking : Lorsqu'une sous-chaîne est choisie, nous pouvons continuer à choisir la sous-chaîne suivante. Si nous atteignons un point où aucune autre sous-chaîne ne peut être formée sans répétition, nous revenons en arrière.
4. Cas de base : Si nous atteignons la fin de la chaîne, nous comptons les sous-chaînes uniques formées.

Implémentons cette solution en PHP : 1593. Diviser une chaîne en nombre maximum de sous-chaînes uniques

maxUniqueSplit("ababccc"); // Output: 5
echo "\n";
echo $solution->maxUniqueSplit("aba"); // Output: 2
echo "\n";
echo $solution->maxUniqueSplit("aa"); // Output: 1
?>





  
  
  Explication:



Signature de fonction : La fonction principale est maxUniqueSplit, qui initialise le processus de retour en arrière.

Retour en arrière :


La fonction backtrack prend la chaîne, le tableau des sous-chaînes utilisées et l'index de départ actuel.
Si l'index de début atteint la fin de la chaîne, il renvoie le nombre de sous-chaînes uniques collectées.
Une boucle parcourt les indices de fin possibles pour créer des sous-chaînes à partir de l'index de début.
Si la sous-chaîne est unique (pas déjà dans le tableau utilisé), elle est ajoutée à used et la fonction récure pour l'index suivant.
Après avoir exploré ce chemin, il supprime la sous-chaîne pour revenir en arrière et explorer d'autres possibilités.


Sortie : La fonction renvoie le nombre maximum de sous-chaînes uniques pour diverses chaînes d'entrée.



  
  
  Complexité



La complexité temporelle peut être élevée en raison de la nature du backtracking, notamment pour les chaînes plus longues, mais compte tenu des contraintes (longueur maximale de 16), cette solution est suffisamment efficace pour les limites de saisie.


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!