Déplacer les pièces pour obtenir une chaîne

2337. Déplacez les pièces pour obtenir une chaîne

Difficulté :Moyen

Sujets : Deux pointeurs, chaîne

Vous recevez deux chaînes start et target, toutes deux de longueur n. Chaque chaîne se compose uniquement des caractères « L », « R » et « _ » où :

• Les caractères 'L' et 'R' représentent des pièces, où une pièce 'L' peut se déplacer vers la gauche seulement s'il y a un espace blanc directement à sa gauche, et une pièce 'R' peut se déplacer vers la droite seulement s'il y a un espace vierge directement à sa c'est vrai.
• Le caractère '_' représente un espace vide qui peut être occupé par n'importe laquelle des pièces 'L' ou 'R'.

Retour true s'il est possible d'obtenir la chaîne cible en déplaçant les morceaux de la chaîne start un certain nombre de fois. Sinon, retournez false.

Exemple 1 :

• Entrée : start = "LRR", cible = "L______RR"
• Sortie : vrai
• Explication : Nous pouvons obtenir la cible de la chaîne dès le départ en effectuant les mouvements suivants :
  • Déplacez la première pièce d'un pas vers la gauche, le début devient égal à "L__RR".
  • Déplacez la dernière pièce d'un pas vers la droite, le début devient égal à "L_R_R".
  • Déplacez la deuxième pièce de trois pas vers la droite, le début devient égal à "L______RR".
  • Puisqu'il est possible d'obtenir la chaîne cible dès le début, nous renvoyons true.

Exemple 2 :

• Entrée : start = "R_L_", target = "__LR"
• Sortie : faux
• Explication : Le morceau 'R' au début de la chaîne peut se déplacer d'un pas vers la droite pour obtenir "RL".
  • Après cela, plus aucune pièce ne peut bouger, il est donc impossible d'obtenir la cible de la corde dès le départ.

Exemple 3 :

• Entrée : start = "R", cible = "R"
• Sortie : faux
• Sortie : Le morceau au début de la chaîne ne peut se déplacer que vers la droite, il est donc impossible d'obtenir la cible de la chaîne depuis le début.

Contraintes :

• n == start.length == target.length
• 1 <= n <= 10⁵
• le début et la cible sont constitués des caractères « L », « R » et « _ ».

Indice :

1. Après une séquence de mouvements, l'ordre des pièces peut-il changer ?
2. Essayez de faire correspondre chaque pièce en s avec une pièce en e.

Solution :

Nous devons vérifier si nous pouvons transformer le début de la chaîne en cible de la chaîne en déplaçant les pièces (« L » et « R ») selon les règles données. Les principales contraintes à considérer sont :

• 'L' ne peut se déplacer que vers la gauche (et ne peut pas traverser d'autres pièces 'L' ou 'R').
• 'R' ne peut se déplacer que vers la droite (et ne peut pas traverser d'autres pièces 'L' ou 'R').
• Nous pouvons utiliser n'importe quel espace vide (« _ ») pour déplacer les pièces.

Plan:

1. Vérification de la longueur : Tout d'abord, vérifiez si les deux chaînes ont la même longueur. Si ce n'est pas le cas, renvoyez false immédiatement.

2. Vérification de la fréquence des caractères : Le nombre de « L », « R » et « _ » dans la chaîne de départ doit correspondre aux nombres respectifs dans la chaîne cible car les pièces ne peuvent pas être dupliquées ou détruites. , seulement déplacé.

3. Correspondance des pièces à l'aide de deux pointeurs :

   • Traversez les deux chaînes (début et cible).
   • Vérifiez si chaque pièce («L» ou «R») au départ peut se déplacer vers sa position correspondante dans la cible.
   • Plus précisément :
     • 'L' doit toujours se déplacer vers la gauche (c'est-à-dire qu'il ne doit pas être dans une position où une pièce dans la cible doit se déplacer vers la droite).
     • 'R' doit toujours se déplacer vers la droite (c'est-à-dire qu'il ne doit pas être dans une position où une pièce dans la cible doit se déplacer vers la gauche).

Explication de l'algorithme :

1. Filtrer les positions L et R :

   • Supprimez tout _ des deux chaînes start et target pour comparer la séquence de L et R. Si les séquences diffèrent, renvoyez false immédiatement.

2. Traversée à deux pointeurs :

   • Utilisez deux pointeurs pour parcourir les caractères de début et de cible.
   • Assurez-vous que :
     • Pour L, la pièce en départ ne peut se déplacer que gauche, sa position en départ doit donc être supérieure ou égale à sa position en cible.
     • Pour R, la pièce en départ ne peut se déplacer que à droite, sa position en départ doit donc être inférieure ou égale à sa position en cible.

3. Résultat de sortie :

   • Si toutes les conditions sont satisfaites pendant le parcours, renvoie true. Sinon, retournez false.

Implémentons cette solution en PHP : 2337. Déplacez les pièces pour obtenir une chaîne

  
  
  Explication:



Vérifications initiales : Tout d'abord, nous vérifions la longueur des deux chaînes et nous assurons que les nombres de « L » et de « R » sont les mêmes dans les deux chaînes. Sinon, retournez false.

Logique à deux pointeurs : Nous utilisons deux pointeurs, i et j, pour parcourir les deux chaînes :

Sauter les espaces vides (« _ ») car ils n'affectent pas le mouvement des pièces.
Si les caractères en i et j dans start et target diffèrent, renvoie false (car nous ne pouvons pas déplacer les pièces vers des caractères différents).
Si un 'L' est trouvé au début et est à une position supérieure à sa position cible, ou si un 'R' est trouvé au début et est à une position plus petite que sa position cible, renvoie false (puisque 'L' ' ne peut se déplacer que vers la gauche et 'R' ne peut se déplacer que vers la droite).



Cas Edge : La solution gère tous les cas Edge possibles, tels que :


Différents nombres de « L » ou de « R » au départ et à la cible.
Incapacité de déplacer les pièces en raison de contraintes.





  
  
  Complexité temporelle :



La complexité temporelle est O(n), où n est la longueur des chaînes d'entrée. C'est parce que nous parcourons chaque chaîne une seule fois.



  
  
  Complexité spatiale :



La complexité de l'espace est O(1), car nous n'utilisons qu'une quantité fixe d'espace supplémentaire.



  
  
  Analyse de complexité :




Complexité temporelle :


Le filtrage des traits de soulignement prend O(n).
La traversée à deux pointeurs prend O(n).
Global : O(n).



Complexité spatiale :


Deux chaînes ($startNoUnderscore et $targetNoUnderscore) sont créées, chacune de taille O(n).
Global : O(n).





  
  
  Explication des cas de test :




Entrée : _L__R__R_, L______RR


La séquence des correspondances L et R.
Chaque pièce peut être déplacée vers la position requise en suivant les règles.

Sortie : vrai.



Entrée : R_L_, __LR


La séquence des correspondances L et R.
La pièce R ne peut pas bouger vers la gauche ; par conséquent, la transformation est impossible.

Sortie : faux.



Entrée : _R, R_


La pièce R ne peut pas bouger vers la gauche ; par conséquent, la transformation est impossible.

Sortie : faux.




Cette implémentation est efficace et respecte les contraintes du problème, ce qui la rend adaptée aux grandes tailles d'entrée.

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!