2825. Machen Sie eine Subsequenz mit cyclischen Inkrementen

Schwierigkeitsgrad: medium

themen: zwei Zeiger, String

Sie erhalten zwei 0-indexed Strings Str1 und Str2.

In einer Operation wählen Sie eine set von Indizes in str1 und für jeden Index i im set, inkrement Str1 [i] zum nächsten Zeichen cyclisch . Das ist 'A' wird 'B', 'B' wird zu 'c' und so weiter und 'z' wird 'a'.

return wahr, wenn es möglich ist, Str2 zu einer Teilsequenz von Str1 zu machen, indem die Operation höchstens einmal und ansonsten false .

durchgeführt werden.

Anmerkung:

Eine Subquenz eines Zeichens ist ein neuer Zeichenfolge, der aus dem Originalzeichenfolge gebildet wird, indem einige (möglicherweise keine) der Zeichen gelöscht werden, ohne die relativen Positionen der verbleibenden Zeichen zu stören.

Beispiel 1:

• input:
str1 = "abc", str2 = "ad"
• output:
true
• Erläuterung:
  Wählen Sie Index 2 in Str1 aus.
  Inkrementieren Str1 [2], um 'D' zu werden.
  Daher wird Str1 zu "Abd" und Str2 ist jetzt eine Subsequenz. Daher wird wahr zurückgegeben.

Beispiel 2:

• input:
str1 = "zc", str2 = "ad"
• output:
true
• Erläuterung:
  Wählen Sie Indizes 0 und 1 in Str1.
  Inkrementieren Str1 [0], um 'a' zu werden.
  Inkrementieren Str1 [1], um 'D' zu werden.
  Daher wird Str1 zu "ad" und Str2 ist jetzt eine Subsequenz. Daher wird wahr zurückgegeben.

Beispiel 3:

• input:
str1 = "ab", str2 = "d"
• output:
false
• Erläuterung:
  In diesem Beispiel kann gezeigt werden, dass es unmöglich ist, Str2 zu einer Subsequenz von STR1 zu machen, die die Operation höchstens verwendet.
  deshalb wird falsch zurückgegeben.

Einschränkungen:

• ^{1 5}
• ^{1 5}
STR1 und STR2 bestehen nur aus englischen Kleinbuchstaben.

Hinweis:

Betrachten Sie die Indizes, die wir separat erhöhen werden.
Wir können zwei Zeiger beibehalten: Zeiger i für Str1 und Zeiger j für Str2, während sie sicherstellen, dass sie innerhalb der Grenzen der Saiten bleiben.
Wenn sowohl Str1 [i] als auch str2 [j] übereinstimmen, oder wenn inkrementiert Str1 [i] str2 [j] übereinstimmt, erhöhen wir beide Zeiger; Ansonsten erhöhen wir nur Zeiger i.
Es ist möglich, Str2 eine Subsequenz von Str1 zu machen, wenn J am Ende von Str2 liegt, nachdem wir kein Match mehr finden können.

Lösung:

Wir müssen überprüfen, ob wir Str2 zu einer Teilsequenz von STR1 machen können, indem wir höchsten

Erläuterung:

• Wir werden zwei Zeiger verwenden, ich für Str1 und j für Str2.
• Wenn das Zeichen bei str1 [i] str2 [j] übereinstimmt, bewegen wir beide Hinweise weiter vorwärts.
• Wenn Str1 [i] inkrementiert werden kann, um Str2 [j] (zyklisch) zu entsprechen, versuchen wir, sie anzupassen und dann beide Zeiger zu bewegen.
.
• Wenn keine der oben genannten Bedingungen gilt, bewegen wir nur den Zeiger i für Str1.
• Schließlich, wenn wir alle Zeichen von Str2 übereinstimmen können, ist es möglich, Str2 zu einer Untersequenz von Str1 zu machen, sonst nicht.

Lassen Sie uns diese Lösung in PHP implementieren: 2825. Machen Sie eine Subsequenz mit cyclischen Inkrementen

Erläuterung:

1. zwei Zeiger : i und j werden bis zum Start von str1 bzw. str2 initialisiert.
2. passing logic : In der Schleife prüfen wir, ob die Zeichen bei str1 [i] und str2 [j] gleich sind oder ob wir Str1 inkrementieren können.
   • Die zyklische Inkrementbedingung wird mit (ord ($ str1 [$ i]) 1 - ord ('a') % 26 behandelt, der überprüft, ob Str1 [i] inkrementiert werden kann, um Str2 [j] zu entsprechen.
   .
3. subsequence check : Wenn wir vollständig durch str2 iteriert sind (d. H. J == M), bedeutet dies, dass Str2 eine Subquenz von str1 ist. Ansonsten ist es nicht.

Zeitkomplexität:

• Der Algorithmus iteriert einmal durch Str1, und jedes Zeichen in Str2 wird nur einmal überprüft, sodass die Zeitkomplexität o (n) ist, wobei n die Länge von str1 ist.

Raumkomplexität:

• Die Raumkomplexität ist o (1) da wir nur ein paar Zeiger verwenden und keinen zusätzlichen Platz benötigen, der von der Eingabegröße abhängig ist.

Diese Lösung prüft effizient, ob es möglich ist, Str2 zu einer Subsequenz von STR1 mit höchstens einer zyklischen Inkrementoperation zu machen.

wenden Sie sich an links

Wenn Sie diese Serie hilfreich gefunden haben, sollten Sie den repository einen Stern auf Github geben oder den Beitrag in Ihren Lieblingsnetzwerken teilen? Ihre Unterstützung würde mir viel bedeuten!

Wenn Sie mehr hilfreiche Inhalte wie diesen wünschen, können Sie mir gerne folgen:

• linkedIn
• github