Bewegen Sie Teile, um eine Schnur zu erhalten

2337. Bewege Teile, um eine Schnur zu erhalten

Schwierigkeit:Mittel

Themen:Zwei Zeiger, String

Sie erhalten zwei Zeichenfolgen start und target, beide mit der Länge n. Jede Zeichenfolge besteht nur aus den Zeichen „L“, „R“ und „_“, wobei:

• Die Zeichen „L“ und „R“ stellen Figuren dar, wobei sich eine Figur „L“ nur dann nach links bewegen kann, wenn sich direkt links davon ein Leerzeichen befindet. und ein Stück „R“ kann sich nur dann nach rechts bewegen, wenn sich direkt daneben ein Leerzeichen befindet Richtig.
• Das Zeichen „_“ stellt ein Leerzeichen dar, das von beliebigen der „L“- oder „R“-Teile besetzt werden kann.

Gibt true zurück, wenn es möglich ist, das String-Ziel zu erhalten, indem die Teile des String-Anfangs beliebig oft verschoben werden. Andernfalls geben Sie false zurück.

Beispiel 1:

• Eingabe: start = "LRR", Ziel = "L______RR"
• Ausgabe:wahr
• Erklärung: Wir können das String-Ziel von Anfang an erhalten, indem wir die folgenden Schritte ausführen:
  • Bewegen Sie das erste Stück einen Schritt nach links, der Anfang wird gleich „L__RR“.
  • Bewegen Sie das letzte Stück einen Schritt nach rechts, der Anfang wird gleich „L_R_R“.
  • Bewegen Sie das zweite Teil drei Schritte nach rechts, der Anfang wird gleich „L______RR“.
  • Da es möglich ist, das String-Ziel von Anfang an zu erhalten, geben wir true zurück.

Beispiel 2:

• Eingabe: start = „R_L_“, target = „__LR“
• Ausgabe:false
• Erklärung: Das „R“-Teil am Saitenanfang kann einen Schritt nach rechts verschoben werden, um „RL“ zu erhalten.
  • Danach können sich keine Figuren mehr bewegen, sodass es unmöglich ist, das Saitenziel von Anfang an zu erreichen.

Beispiel 3:

• Eingabe: start = "R", target = "R"
• Ausgabe:false
• Ausgabe: Das Teil am String-Anfang kann sich nur nach rechts bewegen, daher ist es unmöglich, das String-Ziel vom Anfang an zu erhalten.

Einschränkungen:

• n == start.length == target.length
• 1 <= n <= 10⁵
• Start und Ziel bestehen aus den Zeichen „L“, „R“ und „_“.

Hinweis:

1. Kann sich nach einer bestimmten Zugfolge die Reihenfolge der Figuren ändern?
2. Versuchen Sie, jedes Teil in s einem Teil in e zuzuordnen.

Lösung:

Wir müssen prüfen, ob wir den Saitenanfang in das Saitenziel umwandeln können, indem wir Teile ('L' und 'R') gemäß den gegebenen Regeln verschieben. Die wichtigsten zu berücksichtigenden Einschränkungen sind:

• 'L' kann sich nur nach links bewegen (und kann andere 'L'- oder 'R'-Teile nicht überqueren).
• 'R' kann sich nur nach rechts bewegen (und kann andere 'L'- oder 'R'-Teile nicht kreuzen).
• Wir können beliebige Leerzeichen ('_') verwenden, um Teile zu verschieben.

Planen:

1. Längenprüfung: Überprüfen Sie zunächst, ob beide Zeichenfolgen die gleiche Länge haben. Wenn dies nicht der Fall ist, geben Sie sofort false zurück.

2. Prüfung der Zeichenhäufigkeit: Die Anzahl der „L“, „R“ und „_“ in der Startzeichenfolge muss mit der jeweiligen Anzahl in der Zielzeichenfolge übereinstimmen, da die Teile nicht dupliziert oder zerstört werden können , nur umgezogen.

3. Stückzuordnung mit zwei Zeigern:

   • Durchqueren Sie beide Saiten (Start und Ziel).
   • Überprüfen Sie, ob sich jedes Stück ('L' oder 'R') am Start zu seiner entsprechenden Position im Ziel bewegen kann.
   • Im Einzelnen:
     • 'L' sollte sich immer nach links bewegen (d. h. es darf sich nicht an einer Position befinden, an der sich eine Figur im Ziel nach rechts bewegen sollte).
     • 'R' sollte sich immer nach rechts bewegen (d. h. es darf sich nicht an einer Position befinden, an der sich eine Figur im Ziel nach links bewegen sollte).

Erklärung des Algorithmus:

1. L- und R-Positionen filtern:

   • Entfernen Sie alle _ aus beiden Zeichenfolgen start und target, um die Sequenz von L und R zu vergleichen. Wenn sich die Sequenzen unterscheiden, geben Sie sofort false zurück.

2. Zwei-Zeiger-Durchquerung:

   • Verwenden Sie zwei Zeiger, um die Zeichen in Start und Ziel zu durchlaufen.
   • Stellen Sie sicher, dass:
     • Für L kann sich das Stück am Anfang nur nach links bewegen, daher sollte seine Position am Anfang größer oder gleich seiner Position am Ziel sein.
     • Für R kann sich das Stück am Anfang nur nach rechts bewegen, daher sollte seine Position am Anfang kleiner oder gleich seiner Position am Ziel sein.

3. Ausgabeergebnis:

   • Wenn beim Durchlaufen alle Bedingungen erfüllt sind, wird true zurückgegeben. Andernfalls geben Sie false zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 2337. Bewegen Sie Teile, um eine Schnur zu erhalten

  
  
  Erläuterung:



Erste Überprüfungen: Zuerst überprüfen wir die Länge beider Zeichenfolgen und stellen sicher, dass die Anzahl von „L“ und „R“ in beiden Zeichenfolgen gleich ist. Wenn nicht, geben Sie false zurück.

Zwei-Zeiger-Logik: Wir verwenden zwei Zeiger, i und j, um beide Strings zu durchlaufen:

Überspringen Sie die Leerzeichen ('_'), da diese die Bewegung der Teile nicht beeinflussen.
Wenn die Zeichen bei i und j in Start und Ziel unterschiedlich sind, geben Sie „false“ zurück (da wir keine Teile auf unterschiedliche Zeichen verschieben können).
Wenn ein „L“ in „Start“ gefunden wird und sich an einer Position befindet, die größer als seine Zielposition ist, oder wenn ein „R“ in „Start“ gefunden wird und sich an einer Position befindet, die kleiner als seine Zielposition ist, geben Sie „false“ zurück (da „L ' kann sich nur nach links bewegen und 'R' kann sich nur nach rechts bewegen).



Randfälle: Die Lösung behandelt alle möglichen Randfälle, wie zum Beispiel:


Unterschiedliche Anzahl von „L“ oder „R“ in Start und Ziel.
Teile können aufgrund von Einschränkungen nicht bewegt werden.





  
  
  Zeitkomplexität:



Die Zeitkomplexität beträgt O(n), wobei n die Länge der Eingabezeichenfolgen ist. Dies liegt daran, dass wir jede Zeichenfolge nur einmal durchlaufen.



  
  
  Raumkomplexität:



Die Raumkomplexität ist O(1), da wir nur eine feste Menge an zusätzlichem Raum verwenden.



  
  
  Komplexitätsanalyse:




Zeitkomplexität:


Das Filtern von Unterstrichen erfordert O(n).
Zwei-Zeiger-Traversal benötigt O(n).
Insgesamt: O(n).



Weltraumkomplexität:


Es werden zwei Zeichenfolgen ($startNoUnderscore und $targetNoUnderscore) erstellt, jede mit der Größe O(n).
Insgesamt: O(n).





  
  
  Erläuterung der Testfälle:




Eingabe: _L__R__R_, L______RR


Die Reihenfolge von L und R stimmt überein.
Jedes Teil kann gemäß den Regeln an die gewünschte Position verschoben werden.

Ausgabe:wahr.



Eingabe: R_L_, __LR


Die Reihenfolge von L und R stimmt überein.
Das R-Stück kann sich nicht nach links bewegen; Daher ist die Transformation unmöglich.

Ausgabe:false.



Eingabe: _R, R_


Das R-Stück kann sich nicht nach links bewegen; Daher ist die Transformation unmöglich.

Ausgabe:false.




Diese Implementierung ist effizient und hält sich an die Problembeschränkungen, sodass sie für große Eingabegrößen geeignet ist.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
        
Das obige ist der detaillierte Inhalt vonBewegen Sie Teile, um eine Schnur zu erhalten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!