. Faire pivoter la chaîne

796. Faire pivoter la chaîne

Difficulté :Facile

Sujets : Chaîne, correspondance de chaînes

Étant donné deux chaînes s et goal, renvoie true si et seulement si s peut devenir goal après un certain nombre de changements sur s.

Un shift sur s consiste à déplacer le caractère le plus à gauche de s vers la position la plus à droite.

• Par exemple, si s = "abcde", alors ce sera "bcdea" après un quart de travail.

Exemple 1 :

• Entrée : s = "abcde", objectif = "cdeab"
• Sortie : vrai

Exemple 2 :

• Entrée : s = "abcde", objectif = "abced"
• Sortie : faux

Contraintes :

• 1 <= s.length, goal.length <= 100
• s et goal sont constitués de lettres anglaises minuscules.

Solution :

Nous pouvons profiter des propriétés de concaténation de chaînes. Plus précisément, si nous concaténons la chaîne s avec elle-même (c'est-à-dire s s), toutes les rotations possibles de s apparaîtront comme des sous-chaînes au sein de cette chaîne concaténée. Cela nous permet de vérifier simplement si goal est une sous-chaîne de s s.

Implémentons cette solution en PHP : 796. Faire pivoter la chaîne

  
  
  Explication:



Vérification de la longueur : Nous vérifions d'abord si les longueurs des s et de l'objectif sont les mêmes. Si ce n'est pas le cas, nous renvoyons immédiatement false, car il est impossible que s se transforme en goal.
Concaténation : Nous concaténons la chaîne s avec elle-même pour créer doubleS.
Vérification de sous-chaîne : Nous utilisons la fonction strpos() pour vérifier si l'objectif existe en tant que sous-chaîne dans doubleS. Si c'est le cas, nous retournons vrai ; sinon, nous renvoyons faux.



  
  
  Complexité:




Complexité temporelle : O(n), où n est la longueur de la chaîne, en raison de la concaténation et de la recherche de sous-chaîne.

Complexité spatiale : O(n) pour la chaîne concaténée.


Cette solution détermine efficacement si une chaîne peut en devenir une autre grâce aux rotations.

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!