Isomorphic Strings

Q: Dlaczego potrzebujesz dwóch map haszujących dla łańcuchów izomorficznych?

Mapowanie z s na t wykrywa sytuację, w której jeden znak z s został przemianowany na dwa różne sposoby. Nie wykryje sytuacji, w której dwa znaki z s zostały przemianowane na ten sam znak, jak w przypadku ab i aa . Mapowanie z t z powrotem na s wykrywa ten przypadek.

Q: Czy izomorfizm jest symetryczny?

Tak. Zmianę nazw jeden do jednego można cofnąć, więc jeśli s zostanie przemianowane na t , odwrócenie każdej nazwy zmienia t z powrotem na s . isIsomorphic(s, t) i isIsomorphic(t, s) zawsze dają ten sam wynik.

ŁatweHaszowanie

+10

Dwa ciągi znaków są izomorficzne, jeśli można zmienić nazwy znaków w pierwszym ciągu tak, aby otrzymać drugi. Każde wystąpienie danego znaku otrzymuje tę samą nową nazwę, dwa różne znaki nigdy nie otrzymują tej samej nazwy, a znak może zachować swoją nazwę. Dla dwóch ciągów znaków s i t o tej samej długości zwróć true, jeśli są izomorficzne, a false, jeśli nie są.

Funkcja

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

sstring: ciąg znaków do zmiany nazwy, litery i cyfry
tstring: ciąg znaków, który należy osiągnąć, o tej samej długości co s
Zwracaboolean: prawda, jeśli zmiana nazw znaków w s na zasadzie jeden do jednego daje t

Ograniczenia

1 ≤ s.length ≤ 2 × 10⁴
t.length == s.length
s i t zawierają wyłącznie angielskie litery i cyfry. Wielkie i małe litery są różnymi znakami.

Przykłady

Wejście: s = "noon"t = "deed"
Wyjście: true
Wyjaśnienie: Zmień nazwę n na d, a o na e. Każda pozycja zgadza się z tą zmianą nazw, a dwie litery otrzymują różne nazwy.

Wejście: s = "moon"t = "deed"
Wyjście: false
Wyjaśnienie: Od lewej do prawej: m staje się d, a o staje się e, a następnie n również musiałoby stać się d. Dwie różne litery nie mogą mieć tej samej nazwy, więc odpowiedź to false.

Wejście: s = "r2d2"t = "c3p3"
Wyjście: true
Wyjaśnienie: r zmienia się w c, 2 zmienia się w 3, a d zmienia się w p. Cyfry również są znakami, a obie 2 zmieniają się w 3.

Pytanie dodatkowe

Czy mając listę słów, potrafisz pogrupować te, które są izomorficzne względem siebie, bez porównywania każdej pary słów?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Zmiana nazw musi działać w obie strony: każdy znak z s zamienia się w jeden znak z t, a każdy znak z t pochodzi od jednego znaku z s. Dwie mapy, po jednej dla każdego kierunku, sprawdzają oba warunki w jednym przebiegu.

Porównaj każdą parę pozycji

Poprawne, ale nie kończy się na największych testach

Intuicja

Zmiana nazw zachowuje równość takich samych znaków i różność różnych znaków. Dlatego dla każdej pary pozycji i i j odpowiedź dla s[i] == s[j] musi być taka sama jak dla t[i] == t[j]. To również wystarczy: jeśli każda para się zgadza, przypisanie każdemu znakowi z s znaku z t na odpowiadających mu pozycjach jest dobrze określone i nigdy nie przypisuje dwóch znakom tej samej nazwy. W moon i deed pozycje 0 i 3 zawierają w s różne litery, ale w t dwukrotnie występuje d, więc odpowiedź to false.

Istnieje około n²/2 par: 2 × 10^8 porównań przy n = 2 × 10^4, jeśli żadna para nie przerwie wcześniej pętli.

Algorytm

Przejdź pętlą przez każdy indeks i, a dla każdego z nich przez każdy późniejszy indeks j.
Ustal, czy s[i] jest równe s[j] oraz czy t[i] jest równe t[j].
Jeśli odpowiedzi są różne, zwróć false.
Po ostatniej parze zwróć true.

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

Dwie mapy, po jednej na każdy kierunek

Intuicja

Buduj mapowanie podczas czytania. sToT zapisuje, czym stał się każdy znak w s, a tToS zapisuje, skąd pochodzi każdy znak w t. Na pozycji i, gdzie a = s[i] i b = t[i], albo oba znaki są nowe i łączysz je ze sobą, albo muszą już wskazywać na siebie nawzajem.

Jedna mapa nie wystarczy. Przy użyciu samego sToT ciągi moon i deed przechodzą, ponieważ żadna litera w s nie jest mapowana na dwa sposoby. Problem polega na tym, że zarówno m, jak i n stają się d, a na pozycji 3 tToS już mówi, że d pochodzi z m.

Każda pozycja wymaga kilku operacji na mapie, więc czas działania wynosi O(n). Kod każdego znaku jest mniejszy niż 128, więc każda mapa może być tablicą zawierającą 128 elementów: O(1) miejsca. Wersje w R i Swift najpierw kopiują ciągi do tablic kodów, co zajmuje O(n).

Algorytm

Utwórz dwie puste mapy: sToT i tToS.
Dla każdego indeksu i przyjmij a = s[i] oraz b = t[i].
Jeśli a nie ma w sToT i b nie ma w tToS, przypisz b do a i a do b.
W przeciwnym razie, jeśli sToT[a] nie jest b lub tToS[b] nie jest a, zwróć false.
Po ostatnim indeksie zwróć true.

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

Pułapki i przypadki brzegowe

Utrzymywanie jednej mapy z s na t. Pasują do niej moon i deed, a także ab i aa.
Porównywanie liczby wystąpień każdego znaku. abcabc i xyzxzy zawierają po dwa wystąpienia trzech znaków, ale drugie b znajduje się nad z, podczas gdy pierwsze znajdowało się nad y.
Traktowanie wielkości liter jako nieistotnej. aA zawiera dwa różne znaki, więc nie może stać się bb.
Dostosowywanie rozmiaru tablic mapowań wyłącznie dla znaków od a do z. Wielkie litery i cyfry wykraczają poza ten zakres; indeksuj za pomocą pełnego kodu znaku, używając 128 wpisów.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu izomorficznych ciągów znaków?

Rozwiązanie z dwiema mapami odczytuje każdą pozycję raz, więc działa w czasie O(n). Mapy przechowują najwyżej jeden wpis dla każdego możliwego znaku — 62 liter i cyfr — więc dodatkowa pamięć wynosi O(1). Porównanie każdej pary pozycji zajmuje O(n²).

Dlaczego potrzebujesz dwóch map haszujących dla łańcuchów izomorficznych?

Mapowanie z s na t wykrywa sytuację, w której jeden znak z s został przemianowany na dwa różne sposoby. Nie wykryje sytuacji, w której dwa znaki z s zostały przemianowane na ten sam znak, jak w przypadku ab i aa. Mapowanie z t z powrotem na s wykrywa ten przypadek.

Czy izomorfizm jest symetryczny?

Tak. Zmianę nazw jeden do jednego można cofnąć, więc jeśli s zostanie przemianowane na t, odwrócenie każdej nazwy zmienia t z powrotem na s. isIsomorphic(s, t) i isIsomorphic(t, s) zawsze dają ten sam wynik.

W jaki jeszcze sposób możesz sprawdzić, czy dwa ciągi znaków są izomorficzne?

Zastąp każdy znak pozycją, na której pojawia się po raz pierwszy, i porównaj wyniki. noon i deed dają w obu przypadkach 0 1 1 0, a moon daje 0 1 1 3. Zajmuje to również O(n) czasu i O(n) pamięci na dwa wzorce.

def isIsomorphic(s, t):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

s = "noon"
t = "deed"

Oczekiwany wynik

true