suchen
HeimBackend-EntwicklungPHP-TutorialMachen Sie einen String mithilfe zyklischer Inkremente zu einer Teilsequenz

Make String a Subsequence Using Cyclic Increments

2825. Machen Sie String mithilfe zyklischer Inkremente zu einer Teilsequenz

Schwierigkeit:Mittel

Themen:Zwei Zeiger, String

Sie erhalten zwei 0-indizierte Zeichenfolgen str1 und str2.

In einer Operation wählen Sie einen Satz von Indizes in str1 aus und erhöhen für jeden Index i im Satz str1[i] zyklisch zum nächsten Zeichen. Das heißt, „a“ wird zu „b“, „b“ wird zu „c“ usw. und „z“ wird zu „a“.

Gib true zurück, wenn es möglich ist, str2 zu einer Teilfolge von str1 zu machen, indem die Operation höchstens einmal ausgeführt wird, andernfalls false.

Hinweis: Eine Teilfolge einer Zeichenfolge ist eine neue Zeichenfolge, die aus der ursprünglichen Zeichenfolge gebildet wird, indem einige (möglicherweise keine) der Zeichen gelöscht werden, ohne die relativen Positionen der verbleibenden Zeichen zu beeinträchtigen.

Beispiel 1:

  • Eingabe: str1 = „abc“, str2 = „ad“
  • Ausgabe:wahr
  • Erklärung: Wählen Sie Index 2 in str1 aus.
    • Str1[2] erhöhen, um zu „d“ zu werden.
    • Daher wird str1 zu „abd“ und str2 ist jetzt eine Teilsequenz. Daher wird true zurückgegeben.

Beispiel 2:

  • Eingabe: str1 = "zc", str2 = "ad"
  • Ausgabe:wahr
  • Erklärung: Wählen Sie die Indizes 0 und 1 in str1 aus.
    • Str1[0] erhöhen, um zu „a“ zu werden.
    • Str1[1] erhöhen, um zu „d“ zu werden.
    • Daher wird str1 zu „ad“ und str2 ist jetzt eine Teilsequenz. Daher wird true zurückgegeben.

Beispiel 3:

  • Eingabe: str1 = „ab“, str2 = „d“
  • Ausgabe:false
  • Erklärung: In diesem Beispiel kann gezeigt werden, dass es unmöglich ist, str2 mit der Operation höchstens einmal zu einer Teilfolge von str1 zu machen.
    • Daher wird false zurückgegeben.

Einschränkungen:

  • 1 5
  • 1 5
  • str1 und str2 bestehen nur aus englischen Kleinbuchstaben.

Hinweis:

  1. Berücksichtigen Sie die Indizes, die wir separat erhöhen werden.
  2. Wir können zwei Zeiger beibehalten: Zeiger i für str1 und Zeiger j für str2, wobei wir sicherstellen, dass sie innerhalb der Grenzen der Zeichenfolgen bleiben.
  3. Wenn sowohl str1[i] als auch str2[j] übereinstimmen oder wenn das Erhöhen von str1[i] mit str2[j] übereinstimmt, erhöhen wir beide Zeiger; andernfalls erhöhen wir nur den Zeiger i.
  4. Es ist möglich, str2 zu einer Teilfolge von str1 zu machen, wenn j am Ende von str2 steht, nachdem wir keine Übereinstimmung mehr finden können.

Lösung:

Wir müssen prüfen, ob wir str2 zu einer Teilfolge von str1 machen können, indem wir höchstens eine zyklische Inkrementierungsoperation für alle Zeichen in str1 durchführen:

Erläuterung:

  • Wir werden zwei Zeiger verwenden, i für str1 und j für str2.
  • Wenn das Zeichen bei str1[i] mit str2[j] übereinstimmt, bewegen wir beide Zeiger nach vorne.
  • Wenn str1[i] erhöht werden kann, um mit str2[j] übereinzustimmen (zyklisch), versuchen wir, sie anzupassen und dann beide Zeiger zu verschieben.
  • Wenn keine der oben genannten Bedingungen zutrifft, bewegen wir nur den Zeiger i für str1.
  • Wenn wir schließlich alle Zeichen von str2 abgleichen können, ist es möglich, str2 zu einer Teilfolge von str1 zu machen, andernfalls nicht.

Lassen Sie uns diese Lösung in PHP implementieren: 2825. Machen Sie einen String mithilfe zyklischer Inkremente zu einer Teilsequenz

<?php /**
 * @param String $str1
 * @param String $str2
 * @return Boolean
 */
function canMakeSubsequence($str1, $str2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage
$str1 = "abc";
$str2 = "ad";
echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: true

$str1 = "zc";
$str2 = "ad";
echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: true

$str1 = "ab";
$str2 = "d";
echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: false
?>

Erläuterung:

  1. Zwei Zeiger: i und j werden auf den Anfang von str1 bzw. str2 initialisiert.
  2. Matching-Logik: Innerhalb der Schleife prüfen wir, ob die Zeichen bei str1[i] und str2[j] gleich sind oder ob wir str1[i] zyklisch erhöhen können, um mit str2[j] übereinzustimmen.
    • Die zyklische Inkrementierungsbedingung wird mit (ord($str1[$i]) 1 - ord('a')) % 26 behandelt, das prüft, ob str1[i] inkrementiert werden kann, um mit str2[j] übereinzustimmen.
  3. Teilsequenzprüfung: Wenn wir str2 vollständig durchlaufen haben (d. h. j == m), bedeutet dies, dass str2 eine Teilfolge von str1 ist. Sonst ist es das nicht.

Zeitkomplexität:

  • Der Algorithmus durchläuft str1 einmal und jedes Zeichen in str2 wird nur einmal überprüft, sodass die zeitliche Komplexität O(n) beträgt, wobei n die Länge von str1 ist.

Raumkomplexität:

  • Die Raumkomplexität ist O(1), da wir nur wenige Zeiger verwenden und keinen zusätzlichen Raum benötigen, der von der Eingabegröße abhängt.

Diese Lösung prüft effizient, ob es möglich ist, str2 mit höchstens einer zyklischen Inkrementierungsoperation zu einer Teilfolge von str1 zu machen.

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 vonMachen Sie einen String mithilfe zyklischer Inkremente zu einer Teilsequenz. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Erklären Sie, wie sich das Lastausgleich auf das Sitzungsmanagement auswirkt und wie es angegangen werden soll.Erklären Sie, wie sich das Lastausgleich auf das Sitzungsmanagement auswirkt und wie es angegangen werden soll.Apr 29, 2025 am 12:42 AM

Lastausgleich beeinflusst das Sitzungsmanagement, kann jedoch durch Sitzungsreplikation, Sitzungsklebrigkeit und zentraler Sitzungsspeicher gelöst werden. 1. Sitzungsreplikationsdaten zwischen Servern. 2. Session Stickiness lenkt Benutzeranfragen auf denselben Server. 3. Zentraler Sitzungsspeicher verwendet unabhängige Server wie Redis, um Sitzungsdaten zu speichern, um die Datenfreigabe zu gewährleisten.

Erläutern Sie das Konzept der Sitzungsperrung.Erläutern Sie das Konzept der Sitzungsperrung.Apr 29, 2025 am 12:39 AM

SessionLockingIsatechniqueUTToensureUsers'SSessionSessionSeSexclusivetooneuseratatim.itiscrialtforpreventingDatacorruptionandSecurityBreachesinmulti-UserApplications

Gibt es Alternativen zu PHP -Sitzungen?Gibt es Alternativen zu PHP -Sitzungen?Apr 29, 2025 am 12:36 AM

Zu den Alternativen zu PHP-Sitzungen gehören Cookies, Token-basierte Authentifizierung, datenbankbasierte Sitzungen und Redis/Memcached. 1. Kookies verwalten Sitzungen, indem sie Daten über den Kunden speichern, was einfach, aber nur gering ist. 2. Altbasierte Authentifizierung verwendet Token, um Benutzer zu überprüfen, was sehr sicher ist, aber zusätzliche Logik erfordert. 3.Database-basiertssesses speichert Daten in der Datenbank, was eine gute Skalierbarkeit aufweist, die Leistung jedoch beeinflusst. V.

Definieren Sie den Begriff 'Sitzung' im Kontext von PHP.Definieren Sie den Begriff 'Sitzung' im Kontext von PHP.Apr 29, 2025 am 12:33 AM

Sessionhijacking bezieht sich auf einen Angreifer, der sich als Benutzer ausgibt, indem die SessionID des Benutzers angezeigt wird. Zu den Präventionsmethoden gehören: 1) Verschlüsseln der Kommunikation mit HTTPS; 2) Überprüfung der Quelle der SessionID; 3) mit einem sicheren Algorithmus zur Sitzung der Sitzung; 4) regelmäßig aktualisieren die SitzungID.

Was ist die vollständige Form von PHP?Was ist die vollständige Form von PHP?Apr 28, 2025 pm 04:58 PM

In dem Artikel werden PHP erörtert, in dem die vollständige Form, Hauptnutzungen in der Webentwicklung, der Vergleich mit Python und Java und seine Lernen des Lernens für Anfänger beschrieben werden.

Wie handelt es sich bei PHP um Formulardaten?Wie handelt es sich bei PHP um Formulardaten?Apr 28, 2025 pm 04:57 PM

PHP behandelt Formdaten mit $ \ _ post und $ \ _ GET Superglobals, wobei die Sicherheit durch Validierung, Bereinigung und sichere Datenbankinteraktionen gewährleistet ist.

Was ist der Unterschied zwischen PHP und ASP.NET?Was ist der Unterschied zwischen PHP und ASP.NET?Apr 28, 2025 pm 04:56 PM

Der Artikel vergleicht PHP und ASP.NET und konzentriert sich auf ihre Eignung für groß angelegte Webanwendungen, Leistungsunterschiede und Sicherheitsfunktionen. Beide sind für große Projekte lebensfähig, aber PHP ist Open-Source und plattformunabhängig, während ASP.NET,

Ist PHP eine Fallempfindlichkeit?Ist PHP eine Fallempfindlichkeit?Apr 28, 2025 pm 04:55 PM

Die Fallempfindlichkeit von PHP variiert: Funktionen sind unempfindlich, während Variablen und Klassen empfindlich sind. Zu den Best Practices gehören eine konsistente Benennung und Verwendung von Fall-unempfindlichen Funktionen für Vergleiche.

See all articles

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

Video Face Swap

Video Face Swap

Tauschen Sie Gesichter in jedem Video mühelos mit unserem völlig kostenlosen KI-Gesichtstausch-Tool aus!

Heiße Werkzeuge

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

SAP NetWeaver Server-Adapter für Eclipse

SAP NetWeaver Server-Adapter für Eclipse

Integrieren Sie Eclipse mit dem SAP NetWeaver-Anwendungsserver.

Herunterladen der Mac-Version des Atom-Editors

Herunterladen der Mac-Version des Atom-Editors

Der beliebteste Open-Source-Editor

SecLists

SecLists

SecLists ist der ultimative Begleiter für Sicherheitstester. Dabei handelt es sich um eine Sammlung verschiedener Arten von Listen, die häufig bei Sicherheitsbewertungen verwendet werden, an einem Ort. SecLists trägt dazu bei, Sicherheitstests effizienter und produktiver zu gestalten, indem es bequem alle Listen bereitstellt, die ein Sicherheitstester benötigen könnte. Zu den Listentypen gehören Benutzernamen, Passwörter, URLs, Fuzzing-Payloads, Muster für vertrauliche Daten, Web-Shells und mehr. Der Tester kann dieses Repository einfach auf einen neuen Testcomputer übertragen und hat dann Zugriff auf alle Arten von Listen, die er benötigt.

SublimeText3 Linux neue Version

SublimeText3 Linux neue Version

SublimeText3 Linux neueste Version