Isomorphic Strings

Q: Warum brauchst du zwei Hash-Maps für isomorphe Zeichenfolgen?

Eine Zuordnung von s zu t erkennt, wenn ein Zeichen von s auf zwei Arten umbenannt wird. Sie erkennt nicht, wenn zwei Zeichen von s in dasselbe Zeichen umbenannt werden, wie bei ab und aa . Die Zuordnung von t zurück zu s erkennt diesen Fall.

LeichtHashing

+10

Zwei Zeichenketten sind isomorph, wenn du die Zeichen der ersten umbenennen kannst, um die zweite zu erhalten. Jedes Vorkommen eines Zeichens erhält denselben neuen Namen, zwei verschiedene Zeichen erhalten niemals denselben Namen, und ein Zeichen kann seinen eigenen Namen behalten. Gib für zwei Zeichenketten s und t gleicher Länge true zurück, wenn sie isomorph sind, und false, wenn sie es nicht sind.

Funktion

isIsomorphic(s: string, t: string) → boolean

sstring: die umzubenennende Zeichenfolge, Buchstaben und Ziffern
tstring: die zu erreichende Zeichenfolge, dieselbe Länge wie s
Gibt zurückboolean: wahr, wenn eine bijektive Umbenennung der Zeichen von s t ergibt

Einschränkungen

1 ≤ s.length ≤ 2 × 10⁴
t.length == s.length
s und t enthalten nur englische Buchstaben und Ziffern. Groß- und Kleinbuchstaben sind unterschiedliche Zeichen.

Beispiele

Eingabe: s = "noon"t = "deed"
Ausgabe: true
Erklärung: Benenne n in d und o in e um. Jede Position stimmt mit dieser Umbenennung überein, und die beiden Buchstaben erhalten unterschiedliche Namen.

Eingabe: s = "moon"t = "deed"
Ausgabe: false
Erklärung: Von links nach rechts wird m zu d und o zu e, und dann müsste n ebenfalls zu d werden. Zwei verschiedene Buchstaben können nicht denselben Namen haben, also lautet die Antwort false.

Eingabe: s = "r2d2"t = "c3p3"
Ausgabe: true
Erklärung: r wird zu c, 2 wird zu 3 und d wird zu p. Ziffern sind auch Zeichen, und beide 2 werden zu 3.

Weiterführende Frage

Gegeben ist eine Liste von Wörtern. Kannst du die Wörter, die zueinander isomorph sind, gruppieren, ohne jedes Wortpaar zu vergleichen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Eine Umbenennung muss in beide Richtungen funktionieren: Jedes Zeichen von s wird zu einem Zeichen von t, und jedes Zeichen von t stammt von einem Zeichen von s. Zwei Zuordnungen, eine pro Richtung, prüfen beides in einem einzigen Durchlauf.

Vergleiche jedes Positionspaar

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Bei einer Umbenennung bleiben gleiche Zeichen gleich und unterschiedliche Zeichen unterschiedlich. Daher muss für jedes Positionspaar i und j s[i] == s[j] dasselbe Ergebnis liefern wie t[i] == t[j]. Das ist auch ausreichend: Wenn jedes Paar übereinstimmt, ist die Umbenennung jedes Zeichens von s in das Zeichen von t an seinen Positionen wohldefiniert und weist niemals zwei Zeichen denselben Namen zu. In moon und deed stehen an den Positionen 0 und 3 in s unterschiedliche Buchstaben, in t jedoch zweimal d, daher lautet die Antwort false.

Es gibt ungefähr n²/2 Paare: 2 × 10^8 Vergleiche bei n = 2 × 10^4, wenn kein Paar die Schleife vorzeitig beendet.

Algorithmus

Durchlaufe jeden Index i und für jeden davon jeden späteren Index j.
Finde heraus, ob s[i] gleich s[j] ist und ob t[i] gleich t[j] ist.
Wenn sich die beiden Antworten unterscheiden, gib false zurück.
Gib nach dem letzten Paar true zurück.

def isIsomorphic(s, t):
    n = len(s)
    for i in range(n):
        for j in range(i + 1, n):
            # Two positions must hold equal characters in s exactly when they do in t
            if (s[i] == s[j]) != (t[i] == t[j]):
                return False
    return True

Zwei Karten, eine pro Richtung

Idee

Erstelle die Umbenennung, während du den Text durchgehst. sToT speichert, in welches Zeichen jedes Zeichen von s umgewandelt wurde, und tToS speichert, von welchem Zeichen jedes Zeichen von t stammt. An Position i, mit a = s[i] und b = t[i], sind entweder beide neu und du verknüpfst sie, oder sie müssen bereits aufeinander verweisen.

Eine Zuordnung reicht nicht aus. Mit nur sToT bestehen moon und deed den Test, weil kein Buchstabe von s auf zwei Arten umbenannt wird. Das Problem ist, dass m und n beide zu d werden und tToS an Position 3 bereits angibt, dass d von m stammt.

Jede Position erfordert einige Zuordnungsoperationen, daher beträgt die Laufzeit O(n). Jeder Zeichencode liegt unter 128, daher kann jede Zuordnung ein Array mit 128 Einträgen sein: O(1) Speicherplatz. Die R- und Swift-Versionen kopieren die Zeichenfolgen zunächst in Code-Arrays, was O(n) benötigt.

Algorithmus

Erstelle zwei leere Maps, sToT und tToS.
Setze für jeden Index i a = s[i] und b = t[i].
Wenn a nicht in sToT und b nicht in tToS enthalten ist, ordne a b und b a zu.
Andernfalls gib false zurück, wenn sToT[a] nicht b oder tToS[b] nicht a ist.
Gib nach dem letzten Index true zurück.

def isIsomorphic(s, t):
    s_to_t = {}  # the character of t that each character of s became
    t_to_s = {}  # the character of s that each character of t came from
    for a, b in zip(s, t):
        if a not in s_to_t and b not in t_to_s:
            s_to_t[a] = b
            t_to_s[b] = a
        elif s_to_t.get(a) != b or t_to_s.get(b) != a:
            return False  # a already has another target, or b another source
    return True

Stolperfallen und Grenzfälle

Eine Zuordnung von s zu t beibehalten. Sie akzeptiert moon und deed sowie ab und aa.
Vergleichen, wie oft jedes Zeichen vorkommt. abcabc und xyzxzy verwenden beide jeweils dreimal zwei Zeichen, dennoch steht das zweite b über z, während das erste über y stand.
Groß- und Kleinschreibung als gleich behandeln. aA enthält zwei verschiedene Zeichen und kann daher nicht zu bb werden.
Die Arrays für Zuordnungen nur für a bis z dimensionieren. Großbuchstaben und Ziffern liegen außerhalb dieses Bereichs; verwende den vollständigen Zeichencode als Index und 128 Einträge.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von isomorphen Zeichenfolgen?

Die Lösung mit zwei Maps liest jede Position einmal, daher läuft sie in O(n) Zeit. Die Maps enthalten höchstens einen Eintrag pro möglichem Zeichen, also 62 Buchstaben und Ziffern; der zusätzliche Speicherbedarf beträgt daher O(1). Der Vergleich jedes Positionspaars benötigt O(n²).

Warum brauchst du zwei Hash-Maps für isomorphe Zeichenfolgen?

Eine Zuordnung von s zu t erkennt, wenn ein Zeichen von s auf zwei Arten umbenannt wird. Sie erkennt nicht, wenn zwei Zeichen von s in dasselbe Zeichen umbenannt werden, wie bei ab und aa. Die Zuordnung von t zurück zu s erkennt diesen Fall.

Ist Isomorphismus symmetrisch?

Ja. Eine bijektive Umbenennung kann rückgängig gemacht werden. Wenn s in t umbenannt wird, führt das Umkehren aller Namen t zurück zu s. isIsomorphic(s, t) und isIsomorphic(t, s) stimmen immer überein.

Wie kannst du sonst noch überprüfen, ob zwei Zeichenfolgen isomorph sind?

Ersetze jedes Zeichen durch die Position, an der es zum ersten Mal vorkommt, und vergleiche die Ergebnisse. noon und deed werden beide zu 0 1 1 0, während moon zu 0 1 1 3 wird. Der Zeitaufwand beträgt ebenfalls O(n), der Speicherbedarf für die beiden Muster O(n).

def isIsomorphic(s, t):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

s = "noon"
t = "deed"

Erwartete Ausgabe

true