Jewels and Stones

Q: Apa kompleksitas waktu dari Jewels and Stones?

Dengan set, kompleksitasnya adalah O(j + s) : j langkah untuk membuat set dari jewels dan satu pencarian berwaktu konstan untuk setiap s batu. Memindai jewels untuk setiap batu memiliki kompleksitas O(j × s) .

Q: Bisakah kamu menyelesaikannya tanpa set?

Ya. Huruf-hurufnya adalah huruf Inggris, jadi array berisi 128 penanda yang diindeks berdasarkan kode karakter berfungsi sebagai set tanpa hashing. Tandai setiap huruf permata, lalu hitung batu yang penandanya telah disetel.

PemulaHashing

+10

Kamu mendapatkan dua string yang terdiri dari huruf. Setiap huruf dalam jewels menunjukkan satu jenis permata, dan tidak ada huruf yang berulang. Setiap huruf dalam stones adalah satu batu yang kamu miliki. Kembalikan jumlah batumu yang merupakan permata. Huruf membedakan huruf besar dan kecil: "a" dan "A" adalah jenis yang berbeda.

Fungsi

numJewelsInStones(jewels: string, stones: string) → integer

jewelsstring: jenis batu yang dianggap sebagai permata, satu huruf untuk masing-masing
stonesstring: batu yang kamu miliki, masing-masing satu huruf
Mengembalikaninteger: jumlah batu yang hurufnya muncul pada permata

Batasan

1 ≤ jewels.length ≤ 52
1 ≤ stones.length ≤ 10⁴
Kedua string hanya berisi huruf bahasa Inggris, huruf kecil dan huruf besar.
Semua huruf dalam jewels berbeda.

Contoh

Input: jewels = "rR"stones = "rubyRRr"
Output: 4
Penjelasan: Jenis permatanya adalah r dan R. Dalam rubyRRr, batu r, R, R, dan r cocok, sedangkan u, b, dan y tidak, jadi jawabannya adalah 4.

Input: jewels = "z"stones = "ZZZ"
Output: 0
Penjelasan: Satu-satunya jenis permata adalah z huruf kecil. Setiap batu adalah Z huruf besar, jenis yang berbeda, jadi tidak ada yang dihitung.

Petunjuk

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

0 dari 3 dibuka

Solusi

Untuk setiap batu, kamu mengajukan satu pertanyaan: apakah huruf ini permata? Mencari setiap batu di dalam string jewels akan mengulangi pemindaian yang sama. Masukkan huruf-huruf permata ke dalam set satu kali, lalu setiap batu hanya perlu satu kali pencarian.

Pindai permata untuk menemukan setiap batu

Intuisi

Untuk setiap batu, telusuri jewels dan berhenti pada huruf pertama yang sama. Jika cocok, tambahkan 1 ke hitungan. Berhenti di sana aman karena semua huruf permata berbeda, sehingga satu batu paling banyak cocok dengan satu huruf. Pada contoh pertama, batu u dibandingkan dengan r dan R, tetapi tidak menambah hitungan.

Dengan j jenis permata dan s batu, ada hingga j × s perbandingan. Karena j ≤ 52, 10^4 batu memerlukan sekitar 5 × 10^5 perbandingan, yang cukup cepat untuk kasus ini. Biayanya bertambah seiring jumlah jenis, karena pencarian yang sama dijalankan lagi untuk setiap batu.

Algoritma

Atur count ke 0.
Untuk setiap batu, bandingkan dengan setiap huruf dalam jewels.
Saat menemukan huruf yang sama untuk pertama kalinya, tambahkan 1 ke count lalu lanjutkan ke batu berikutnya.
Kembalikan count.

def numJewelsInStones(jewels, stones):
    count = 0
    for stone in stones:
        for jewel in jewels:
            if stone == jewel:
                count += 1
                break  # the kinds are distinct: no second match is possible
    return count

Masukkan permata ke dalam set

Intuisi

Jawaban untuk "apakah huruf ini adalah permata?" tidak pernah berubah untuk setiap huruf, jadi hitung sekali untuk tiap jenis: buat set dari huruf-huruf dalam jewels. Set menjawab keanggotaan dalam waktu konstan, jadi setiap batu hanya memerlukan satu pencarian, bukan pemindaian.

Untuk contoh pertama, set-nya adalah {r, R}. Saat menelusuri rubyRRr, hasil pencariannya adalah ya, tidak, tidak, tidak, ya, ya, ya: empat permata. Membuat set memerlukan j langkah dan penelusuran memerlukan s, jadi totalnya adalah O(j + s). Dalam bahasa tanpa set bawaan, array berisi penanda yang diindeks berdasarkan kode karakter melakukan hal yang sama.

Algoritma

Buat set yang berisi setiap huruf dari jewels.
Atur count ke 0.
Untuk setiap batu, tambahkan 1 ke count jika set berisi batu tersebut.
Kembalikan count.

def numJewelsInStones(jewels, stones):
    kinds = set(jewels)
    count = 0
    for stone in stones:
        if stone in kinds:
            count += 1
    return count

Jebakan dan kasus tepi

Mengabaikan huruf besar dan kecil. Mengubah kedua string menjadi huruf kecil membuat z cocok dengan Z, dan contoh kedua menghasilkan 3, bukan 0.
Menghitung jenis permata yang berbeda, bukan batu permata. rubyRRr memiliki dua jenis permata, tetapi empat batu permata; pengulangan tetap dihitung.
Membuat set di dalam perulangan batu. Ini membutuhkan j langkah untuk setiap batu dan membuat kompleksitasnya kembali menjadi O(j × s).
Menukar argumen. Set harus berisi jewels dan perulangan harus menelusuri stones. Jika dibalik, ("a", "aaa") menghasilkan 1, bukan 3.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Jewels and Stones?

Dengan set, kompleksitasnya adalah O(j + s): j langkah untuk membuat set dari jewels dan satu pencarian berwaktu konstan untuk setiap s batu. Memindai jewels untuk setiap batu memiliki kompleksitas O(j × s).

Mengapa menggunakan hash set untuk Jewels and Stones?

Setiap batu bertanya apakah hurufnya adalah permata. Hash set menjawab dalam waktu konstan, sedangkan pencarian pada string jewels membutuhkan waktu yang sebanding dengan panjangnya. Kamu cukup membayar sekali untuk membuat set dan menghemat waktu untuk setiap batu setelahnya.

Bisakah kamu menyelesaikannya tanpa set?

Ya. Huruf-hurufnya adalah huruf Inggris, jadi array berisi 128 penanda yang diindeks berdasarkan kode karakter berfungsi sebagai set tanpa hashing. Tandai setiap huruf permata, lalu hitung batu yang penandanya telah disetel.

def numJewelsInStones(jewels, stones):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

jewels = "rR"
stones = "rubyRRr"

Output yang diharapkan