Isomorphic Strings

Q: Mengapa kamu memerlukan dua hash map untuk string isomorfik?

Pemetaan dari s ke t menangkap satu karakter s yang diganti dengan dua cara. Pemetaan itu tidak bisa mendeteksi dua karakter s yang diganti menjadi karakter yang sama, seperti pada ab dan aa . Pemetaan dari t kembali ke s menangkap kasus tersebut.

Q: Apakah isomorfisme bersifat simetris?

Ya. Penggantian nama satu-ke-satu bisa dibalik, jadi jika s diubah namanya menjadi t , membalik setiap nama akan mengubah t kembali menjadi s . isIsomorphic(s, t) dan isIsomorphic(t, s) selalu menghasilkan jawaban yang sama.

MudahHashing

+10

Dua string disebut isomorfik jika kamu dapat mengganti nama karakter pada string pertama untuk mendapatkan string kedua. Setiap kemunculan karakter mendapat nama baru yang sama, dua karakter berbeda tidak pernah mendapat nama yang sama, dan karakter boleh tetap menggunakan namanya sendiri. Untuk dua string s dan t yang panjangnya sama, kembalikan true jika keduanya isomorfik dan false jika tidak.

Fungsi

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

sstring: string yang akan diganti namanya, huruf dan angka
tstring: string yang harus dicapai, dengan panjang yang sama dengan s
Mengembalikanboolean: benar jika pemetaan satu-ke-satu karakter dari s menghasilkan t

Batasan

1 ≤ s.length ≤ 2 × 10⁴
t.length == s.length
s dan t hanya berisi huruf dan angka. Huruf besar dan huruf kecil adalah karakter yang berbeda.

Contoh

Input: s = "noon"t = "deed"
Output: true
Penjelasan: Ubah nama n menjadi d dan o menjadi e. Setiap posisi cocok dengan perubahan nama tersebut, dan kedua huruf mendapatkan nama yang berbeda.

Input: s = "moon"t = "deed"
Output: false
Penjelasan: Dari kiri ke kanan, m menjadi d dan o menjadi e, lalu n juga harus menjadi d. Dua huruf yang berbeda tidak bisa memiliki nama yang sama, jadi jawabannya adalah false.

Input: s = "r2d2"t = "c3p3"
Output: true
Penjelasan: r menjadi c, 2 menjadi 3 dan d menjadi p. Digit juga merupakan karakter, dan kedua 2 menjadi 3.

Pertanyaan lanjutan

Diberikan sebuah list kata, bisakah kamu mengelompokkan kata-kata yang saling isomorfik tanpa membandingkan setiap pasangan kata?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Penggantian nama harus berlaku dua arah: setiap karakter s berubah menjadi satu karakter t, dan setiap karakter t berasal dari satu karakter s. Dua pemetaan, satu untuk setiap arah, memeriksa keduanya dalam satu kali lintasan.

Bandingkan setiap pasangan posisi

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Penggantian nama mempertahankan karakter yang sama tetap sama dan karakter yang berbeda tetap berbeda. Jadi, untuk setiap pasangan posisi i dan j, s[i] == s[j] harus memberikan jawaban yang sama dengan t[i] == t[j]. Itu juga sudah cukup: jika setiap pasangan cocok, penggantian setiap karakter s dengan karakter t pada posisinya terdefinisi dengan baik dan tidak pernah memberikan satu nama untuk dua karakter. Dalam moon dan deed, posisi 0 dan 3 berisi huruf berbeda dalam s, tetapi huruf d sebanyak dua kali dalam t, jadi jawabannya adalah false.

Ada sekitar n²/2 pasangan: 2 × 10^8 perbandingan pada n = 2 × 10^4 jika tidak ada pasangan yang menghentikan perulangan lebih awal.

Algoritma

Lakukan perulangan pada setiap indeks i, lalu untuk setiap indeks, lakukan perulangan pada setiap indeks j setelahnya.
Tentukan apakah s[i] sama dengan s[j], dan apakah t[i] sama dengan t[j].
Jika kedua jawaban berbeda, kembalikan false.
Setelah pasangan terakhir, kembalikan 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

Dua map, masing-masing untuk satu arah

Intuisi

Bangun pemetaan nama baru sambil membaca. Peta sToT mencatat karakter s menjadi apa, dan tToS mencatat asal setiap karakter t. Pada posisi i, dengan a = s[i] dan b = t[i], keduanya harus sama-sama baru agar kamu bisa menghubungkannya, atau keduanya harus sudah saling menunjuk.

Satu peta tidak cukup. Jika hanya menggunakan sToT, moon dan deed lolos, karena tidak ada huruf di s yang diubah menjadi dua cara berbeda. Kesalahannya adalah m dan n sama-sama menjadi d, sedangkan pada posisi 3 tToS sudah mencatat bahwa d berasal dari m.

Setiap posisi memerlukan beberapa operasi peta, jadi waktunya O(n). Kode karakter selalu di bawah 128, jadi setiap peta bisa berupa array dengan 128 entri: ruang O(1). Versi R dan Swift terlebih dahulu menyalin string ke dalam array kode, yang memerlukan O(n).

Algoritma

Buat dua map kosong, sToT dan tToS.
Untuk setiap indeks i, tetapkan a = s[i] dan b = t[i].
Jika a tidak ada di sToT dan b tidak ada di tToS, petakan a ke b dan b ke a.
Jika tidak, apabila sToT[a] bukan b atau tToS[b] bukan a, kembalikan false.
Setelah indeks terakhir, kembalikan 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

Jebakan dan kasus tepi

Mempertahankan satu pemetaan dari s ke t. Pemetaan ini menerima moon dan deed, serta ab dan aa.
Membandingkan berapa kali setiap karakter muncul. abcabc dan xyzxzy sama-sama menggunakan tiga karakter sebanyak dua kali, tetapi b yang kedua berada di atas z, sedangkan sebelumnya berada di atas y.
Menganggap huruf besar dan kecil sama. aA berisi dua karakter yang berbeda, jadi tidak bisa menjadi bb.
Membatasi ukuran array pemetaan hanya untuk a hingga z. Huruf besar dan digit berada di luar rentang itu. Gunakan kode karakter lengkap sebagai indeks dengan 128 entri.

Pertanyaan yang sering diajukan4

Apa kompleksitas waktu dari Isomorphic Strings?

Solusi dengan dua map membaca setiap posisi satu kali, jadi berjalan dalam waktu O(n). Map menyimpan paling banyak satu entri untuk setiap karakter yang mungkin, yaitu 62 huruf dan digit, jadi ruang tambahannya adalah O(1). Membandingkan setiap pasangan posisi membutuhkan O(n²).

Mengapa kamu memerlukan dua hash map untuk string isomorfik?

Pemetaan dari s ke t menangkap satu karakter s yang diganti dengan dua cara. Pemetaan itu tidak bisa mendeteksi dua karakter s yang diganti menjadi karakter yang sama, seperti pada ab dan aa. Pemetaan dari t kembali ke s menangkap kasus tersebut.

Apakah isomorfisme bersifat simetris?

Ya. Penggantian nama satu-ke-satu bisa dibalik, jadi jika s diubah namanya menjadi t, membalik setiap nama akan mengubah t kembali menjadi s. isIsomorphic(s, t) dan isIsomorphic(t, s) selalu menghasilkan jawaban yang sama.

Bagaimana lagi kamu bisa memeriksa apakah dua string isomorfik?

Ganti setiap karakter dengan posisi kemunculan pertamanya, lalu bandingkan hasilnya. noon dan deed sama-sama menjadi 0 1 1 0, sedangkan moon menjadi 0 1 1 3. Kompleksitas waktunya juga O(n), dengan penggunaan memori O(n) untuk kedua pola tersebut.

def isIsomorphic(s, t):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "noon"
t = "deed"

Output yang diharapkan

true