Permutation in String

Q: Apa kompleksitas waktu Permutation in String?

Dengan sliding window, kompleksitasnya O(m + n) , dengan m sebagai panjang s1 dan n sebagai panjang s2 . Kamu menghitung s1 sekali, lalu setiap huruf dalam s2 masuk ke window sekali dan keluar sekali. Menghitung ulang setiap window dari awal membutuhkan biaya O(n · m) .

Q: Apakah Permutation in String sama dengan menemukan anagram di dalam string?

Ya. Permutasi s1 adalah anagram dari s1 , jadi pertanyaannya adalah apakah ada substring dari s2 sepanjang m yang merupakan anagram dari s1 . Pemeriksaan anagram seluruh string membandingkan jumlah kemunculan satu kali, sedangkan di sini pemeriksaan dilakukan pada jendela geser.

SedangSliding window Hashing

+10

Permutasi sebuah string menggunakan huruf yang sama dalam urutan apa pun, masing-masing sebanyak kemunculannya dalam string asli: tar, rat, dan art adalah permutasi satu sama lain. Kamu mendapatkan dua string s1 dan s2 yang terdiri dari huruf kecil bahasa Inggris. Kembalikan true jika salah satu permutasi s1 muncul dalam s2 sebagai substring (rangkaian karakter yang berurutan), dan false jika tidak.

Fungsi

checkInclusion(s1: string, s2: string) → boolean

s1string: huruf-huruf yang harus disusun ulang
s2string: string yang akan dicari
Mengembalikanboolean: true jika sebuah substring dari s2 merupakan penyusunan ulang s1

Batasan

1 ≤ s1.length ≤ 2 × 10⁴
1 ≤ s2.length ≤ 5 × 10⁴
s1 dan s2 hanya berisi huruf kecil bahasa Inggris (a sampai z).
s1 bisa lebih panjang daripada s2.

Contoh

Input: s1 = "tar"s2 = "smartphone"
Output: true
Penjelasan: Substring art pada indeks 2 hingga 4 dari smartphone berisi satu a, satu r, dan satu t, huruf yang sama dengan tar.

Input: s1 = "noon"s2 = "onion"
Output: false
Penjelasan: Jendela dengan panjang 4 adalah onio dan nion. noon memerlukan dua n dan dua o, sedangkan setiap jendela memiliki i sebagai pengganti salah satunya.

Input: s1 = "abcd"s2 = "dcb"
Output: false
Penjelasan: Setiap permutasi abcd memiliki 4 huruf, sedangkan dcb hanya memiliki 3 huruf, jadi dcb tidak mungkin memuatnya.

Pertanyaan lanjutan

Bisakah kamu mengembalikan setiap indeks tempat permutasi s1 dimulai di dalam s2, dengan waktu tetap O(m + n)?

Petunjuk

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

0 dari 3 dibuka

Solusi

Mencantumkan semua permutasi tidak mungkin dilakukan: 10 huruf saja sudah memiliki 3,628,800 susunan. Abaikan urutan. Substring dari s2 merupakan permutasi dari s1 tepat ketika panjangnya m dan jumlah setiap hurufnya sama. Jadi, geser satu window sepanjang m melintasi s2, perbarui jumlah hurufnya dengan menambahkan satu huruf dan mengeluarkan satu huruf pada setiap langkah.

Hitung setiap jendela dari awal

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Hitung huruf-huruf dalam s1 satu kali dalam tabel berisi 26 angka. Lalu, ambil setiap substring s2 dengan panjang m, hitung huruf-hurufnya dalam tabel baru, lalu bandingkan. Dalam smartphone, jendelanya adalah sma, mar, art, dan seterusnya, dan art cocok dengan tar.

Cara ini memeriksa setiap kandidat, jadi hasilnya benar. Namun, jendela yang bersebelahan memiliki m-1 huruf yang sama, dan kamu menghitung ulang semuanya: dengan m = 2 × 10^4 dan n = 5 × 10^4, ada 30,001 jendela yang masing-masing berisi 20,000 huruf, sekitar 6 × 10^8 langkah.

Algoritma

Jika s1 lebih panjang daripada s2, kembalikan false.
Hitung huruf-huruf dalam s1 pada tabel need yang berisi 26 nol.
Untuk setiap indeks awal dari 0 hingga n-m, hitung huruf-huruf dari m karakter mulai dari indeks tersebut pada tabel baru.
Jika tabel itu sama dengan need, kembalikan true.
Setelah jendela terakhir, kembalikan false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26  # need[0] is 'a', need[25] is 'z'
    for ch in s1:
        need[ord(ch) - 97] += 1
    for start in range(n - m + 1):
        # Count the letters of s2[start : start + m] from scratch
        window = [0] * 26
        for i in range(start, start + m):
            window[ord(s2[i]) - 97] += 1
        if window == need:
            return True
    return False

Geser jendela dan bandingkan hitungan 26

Intuisi

Jendela yang bersebelahan berbeda dalam dua huruf: perpindahan dari mar ke art menghapus m dan menambahkan t. Jadi, gunakan satu tabel untuk jendela saat ini dan ubah tabel itu dengan satu pembaruan +1 dan satu pembaruan -1 pada setiap langkah.

Setiap langkah memerlukan dua pembaruan dan perbandingan 26 angka, berapa pun nilai m: sekitar 26 × 50,000 = 1.3 × 10^6 operasi pada input terbesar.

Algoritma

Jika s1 lebih panjang daripada s2, kembalikan false.
Hitung kemunculan huruf dalam s1 ke dalam need dan kemunculan m huruf pertama s2 ke dalam window.
Jika kedua tabel sama, kembalikan true.
Untuk setiap i dari m hingga n-1: tambahkan 1 untuk s2[i], kurangi 1 untuk s2[i-m], lalu kembalikan true jika tabelnya sama.
Kembalikan false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26
    window = [0] * 26
    for i in range(m):
        need[ord(s1[i]) - 97] += 1
        window[ord(s2[i]) - 97] += 1  # the first window is s2[0 : m]
    if window == need:
        return True
    for i in range(m, n):
        window[ord(s2[i]) - 97] += 1      # s2[i] enters on the right
        window[ord(s2[i - m]) - 97] -= 1  # s2[i - m] leaves on the left
        if window == need:
            return True
    return False

Geser jendelanya dan lacak huruf yang tidak seimbang

Intuisi

Satu langkah hanya mengubah dua hitungan, jadi membandingkan semuanya sebanyak 26 kali akan mengulangi pekerjaan. Simpan balance[c], jumlah kemunculan c di s1 dikurangi jumlah kemunculannya di dalam window, dan unbalanced, jumlah huruf yang balance-nya bukan 0. Window adalah permutasi dari s1 tepat ketika unbalanced bernilai 0.

Satu aturan menjaga penghitung tetap benar: sebelum kamu mengubah balance, tambahkan 1 ke unbalanced jika nilainya 0; setelahnya, kurangi 1 jika nilainya 0. Perubahan dari 2 ke 1 tidak memicu keduanya, dan itu benar. Untuk tar di smartphone, unbalanced dimulai dari 3. s dan m menaikkan nilainya menjadi 5, a menurunkannya menjadi 4, r masuk dan s keluar sehingga nilainya menjadi 2, lalu t masuk dan m keluar sehingga nilainya menjadi 0 pada art.

Kamu bisa menguji mulai dari huruf pertama: selama window lebih pendek daripada m, jumlah balance bernilai positif, jadi salah satunya bukan 0.

Algoritma

Jika s1 lebih panjang daripada s2, kembalikan false.
Hitung s1 ke dalam balance dan atur unbalanced ke jumlah huruf dengan balance selain 0.
Untuk setiap indeks i dari s2, kurangi 1 dari balance s2[i], tambahkan 1 ke unbalanced jika balance tersebut sebelumnya 0, dan kurangi 1 jika nilainya menjadi 0.
Jika i ≥ m, tambahkan 1 ke balance s2[i-m] dengan pencatatan yang sama.
Jika unbalanced adalah 0, kembalikan true. Setelah perulangan, kembalikan false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    # balance[c]: copies of letter c in s1 minus copies in the window
    balance = [0] * 26
    for ch in s1:
        balance[ord(ch) - 97] += 1
    unbalanced = sum(1 for b in balance if b != 0)
    for i in range(n):
        # s2[i] enters the window on the right
        c = ord(s2[i]) - 97
        if balance[c] == 0:
            unbalanced += 1
        balance[c] -= 1
        if balance[c] == 0:
            unbalanced -= 1
        # s2[i - m] leaves on the left once the window would pass m letters
        if i >= m:
            c = ord(s2[i - m]) - 97
            if balance[c] == 0:
                unbalanced += 1
            balance[c] += 1
            if balance[c] == 0:
                unbalanced -= 1
        if unbalanced == 0:
            return True
    return False

Jebakan dan kasus tepi

Hanya memeriksa apakah setiap huruf dari s1 ada di dalam jendela. onio memuat setiap huruf dari noon, tetapi bukan permutasi dari kata tersebut.
Menghapus huruf yang salah. Saat s2[i] masuk, s2[i-m] keluar. Menghapus s2[i-m+1] akan membuang huruf yang masih berada di dalam jendela.
Melewatkan jendela pertama. Jika kamu hanya membandingkan setelah menggeser jendela, tar pada indeks 0 dari tarp tidak akan pernah ditemukan.
Tidak langsung mengembalikan false saat s1 lebih panjang daripada s2. Di Rust, n - m pada panjang bertipe unsigned akan mengalami underflow, dan di Swift, rentang 0...(n - m) akan menyebabkan crash.
Membandingkan array dengan == saat operator itu membandingkan referensi, seperti di JavaScript dan Dart. Di Java, gunakan Arrays.equals.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu Permutation in String?

Dengan sliding window, kompleksitasnya O(m + n), dengan m sebagai panjang s1 dan n sebagai panjang s2. Kamu menghitung s1 sekali, lalu setiap huruf dalam s2 masuk ke window sekali dan keluar sekali. Menghitung ulang setiap window dari awal membutuhkan biaya O(n · m).

Apakah Permutation in String sama dengan menemukan anagram di dalam string?

Ya. Permutasi s1 adalah anagram dari s1, jadi pertanyaannya adalah apakah ada substring dari s2 sepanjang m yang merupakan anagram dari s1. Pemeriksaan anagram seluruh string membandingkan jumlah kemunculan satu kali, sedangkan di sini pemeriksaan dilakukan pada jendela geser.

Bisakah saya menggunakan hash map sebagai pengganti array yang berisi 26 penghitung?

Ya, dan kamu memerlukannya jika string dapat memuat karakter apa pun. Jika hanya menggunakan huruf kecil, array berukuran 26 lebih cepat. Dengan map, hapus sebuah key saat jumlahnya turun menjadi 0 agar map dengan huruf yang sama bisa dibandingkan sebagai setara, atau gunakan penghitung unbalanced, yang bekerja dengan cara yang sama pada map.

def checkInclusion(s1, s2):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s1 = "tar"
s2 = "smartphone"

Output yang diharapkan

true

Permutation in String

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Hitung setiap jendela dari awal

Geser jendela dan bandingkan hitungan 26

Geser jendelanya dan lacak huruf yang tidak seimbang

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa