Valid Anagram

Q: Berapa kompleksitas waktu Valid Anagram?

Menghitung huruf membutuhkan waktu O(n) dan ruang tambahan O(1) , karena array penghitung memiliki 26 entri, berapa pun panjang string-nya. Mengurutkan kedua string membutuhkan waktu O(n log n) dan biasanya ruang O(n) untuk salinan yang sudah diurutkan.

Q: Apakah lebih baik mengurutkan atau menghitung saat memeriksa anagram?

Menghitung lebih cepat secara teoretis, O(n) dibandingkan O(n log n) , dan prosesnya dapat berhenti segera setelah satu huruf digunakan terlalu sering. Pengurutan lebih singkat untuk ditulis dan berfungsi untuk alfabet apa pun tanpa perubahan. Dalam wawancara, sebutkan pengurutan terlebih dahulu, lalu tingkatkan solusinya dengan menghitung.

MudahHashing Pengurutan

+10

Dua string disebut anagram jika salah satunya merupakan susunan ulang dari yang lain: keduanya menggunakan huruf yang sama, dengan jumlah kemunculan yang sama untuk setiap huruf. Kamu mendapatkan dua string s dan t yang terdiri dari huruf kecil bahasa Inggris. Kembalikan true jika t adalah anagram dari s, dan false jika tidak.

Fungsi

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

sstring: string pertama, huruf kecil
tstring: string yang akan diuji terhadap s
Mengembalikanboolean: benar jika t menggunakan huruf-huruf s secara persis, masing-masing dengan jumlah yang sama

Batasan

1 ≤ s.length, t.length ≤ 2 × 10⁴
s dan t hanya berisi huruf kecil bahasa Inggris (a hingga z).
Panjang keduanya bisa berbeda.

Contoh

Input: s = "listen"t = "silent"
Output: true
Penjelasan: Kedua kata memiliki satu e, i, l, n, s, dan t, jadi silent adalah listen dengan huruf-hurufnya yang diacak.

Input: s = "aabb"t = "abbb"
Output: false
Penjelasan: Panjangnya sama dan keduanya hanya menggunakan a dan b, tetapi aabb memiliki dua a dan abbb memiliki satu, jadi jumlahnya berbeda.

Input: s = "cat"t = "cast"
Output: false
Penjelasan: cast terdiri dari empat huruf dan cat terdiri dari tiga huruf, jadi tidak ada penyusunan ulang cat yang dapat mengejanya.

Pertanyaan lanjutan

Bagaimana jika string dapat menyimpan karakter Unicode apa pun, bukan hanya a sampai z? Bagaimana kamu akan mengubah penghitungannya?

Petunjuk

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

0 dari 3 dibuka

Solusi

Anagram mempertahankan jumlah setiap huruf dan mengabaikan urutannya. Jadi, kamu perlu ringkasan dari setiap string yang tidak mengingat posisi huruf, tetapi mengingat jumlah setiap huruf. Pengurutan membangun ringkasan itu dalam O(n log n); tabel berisi 26 penghitung membangunnya dalam satu kali lintasan.

Urutkan kedua string

Intuisi

Pengurutan menata huruf dalam string menurut urutan alfabet dan menghapus informasi tentang posisi awal setiap huruf. listen dan silent sama-sama menjadi eilnst setelah diurutkan; aabb dan abbb tetap seperti semula dan berbeda pada indeks 1. Dua string memiliki huruf yang sama dengan jumlah kemunculan yang sama persis jika bentuk terurutnya sama.

Bandingkan panjangnya terlebih dahulu dan lewati kedua pengurutan jika panjangnya berbeda. Pengurutan membutuhkan waktu O(n log n) dan, dalam sebagian besar bahasa, ruang O(n) untuk salinan karakternya. Pada n = 2 × 10^4, cara ini cepat, tetapi menghitung membutuhkan lebih sedikit pekerjaan.

Algoritma

Jika panjang s dan t berbeda, kembalikan false.
Salin karakter dari setiap string ke dalam array.
Urutkan kedua array.
Kembalikan true jika kedua array yang telah diurutkan sama, elemen demi elemen.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

Hitung setiap huruf

Intuisi

Karena hanya 26 huruf yang dapat muncul, simpan satu penghitung untuk setiap huruf dalam array berisi 26 elemen, dengan indeks berupa kode karakter dikurangi kode a. Telusuri s sambil menambahkan 1 ke penghitung setiap huruf, lalu telusuri t sambil mengurangi 1.

Penghitung di bawah 0 berarti t menggunakan huruf itu lebih sering daripada s, jadi kamu bisa langsung berhenti. Untuk aabb dan abbb, nilai penghitungnya adalah a: 2, b: 2 setelah s; huruf b ketiga dari t membuat nilai b menjadi -1, lalu kamu mengembalikan false.

Jika tidak ada penghitung yang bernilai negatif, jumlahnya cocok. Panjang kedua string sama, jadi jumlah semua penghitung adalah 0 setelah kedua penelusuran; jika tidak ada yang negatif, nilai positif tidak akan memiliki nilai lain untuk menyeimbangkannya, sehingga semuanya bernilai 0. Itulah sebabnya pemeriksaan panjang merupakan bagian dari pembuktian, bukan jalan pintas.

Setiap string dibaca satu kali, dengan waktu O(n), dan array menyimpan 26 angka berapa pun panjangnya, dengan ruang tambahan O(1).

Algoritma

Jika panjang s dan t berbeda, kembalikan false.
Buat array berisi 26 angka nol.
Untuk setiap huruf dalam s, tambahkan 1 ke pencacahnya.
Untuk setiap huruf dalam t, kurangi 1 dari pencacahnya. Jika nilainya turun di bawah 0, kembalikan false.
Kembalikan true.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for ch in t:
        index = ord(ch) - ord("a")
        counts[index] -= 1
        if counts[index] < 0:
            return False  # t uses this letter more often than s
    return True

Jebakan dan kasus tepi

Membandingkan kumpulan huruf. aabb dan abbb sama-sama hanya menggunakan a dan b, tetapi keduanya bukan anagram.
Memeriksa apakah setiap huruf dalam t muncul di suatu tempat dalam s tanpa mencoretnya. aab dan abb lolos pemeriksaan itu untuk kedua arah.
Melewatkan pemeriksaan panjang dalam versi penghitungan. Dengan s = ab dan t = a, tidak ada pencacah yang nilainya kurang dari 0, sehingga kode keliru mengembalikan true.
Mengindeks array pencacah menggunakan kode karakter mentah. Nilai a adalah 97, jauh melewati akhir array berukuran 26. Kurangi dahulu dengan kode a, lalu di Lua dan R tambahkan 1 karena array-nya dimulai dari 1.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Valid Anagram?

Menghitung huruf membutuhkan waktu O(n) dan ruang tambahan O(1), karena array penghitung memiliki 26 entri, berapa pun panjang string-nya. Mengurutkan kedua string membutuhkan waktu O(n log n) dan biasanya ruang O(n) untuk salinan yang sudah diurutkan.

Apakah lebih baik mengurutkan atau menghitung saat memeriksa anagram?

Menghitung lebih cepat secara teoretis, O(n) dibandingkan O(n log n), dan prosesnya dapat berhenti segera setelah satu huruf digunakan terlalu sering. Pengurutan lebih singkat untuk ditulis dan berfungsi untuk alfabet apa pun tanpa perubahan. Dalam wawancara, sebutkan pengurutan terlebih dahulu, lalu tingkatkan solusinya dengan menghitung.

Mengapa menggunakan satu array penghitung alih-alih dua?

Dua array, masing-masing untuk satu string, juga bisa digunakan: hitung setiap string, lalu bandingkan array-nya. Satu array yang nilainya bertambah untuk s dan berkurang untuk t menggunakan setengah memori dan memungkinkan kamu mengembalikan false begitu sebuah penghitung menjadi negatif, tanpa perulangan perbandingan terakhir.

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

Tes #1

Tes #2

Tes #3

Argumen

s = "listen"
t = "silent"

Output yang diharapkan

true