Count a Character

+10

Kamu mendapatkan string s dan satu huruf c. Kembalikan jumlah kemunculan c di dalam s. Pencocokan membedakan huruf besar dan kecil: B dan b adalah karakter yang berbeda.

Fungsi

countChar(s: string, c: string) → integer

sstring: string huruf bahasa Inggris yang dicari
cstring: satu huruf untuk dihitung
Mengembalikaninteger: berapa banyak karakter dalam s yang sama dengan c

Batasan

1 ≤ s.length ≤ 5 × 10⁴
s hanya berisi huruf Inggris (a sampai z, A sampai Z).
c adalah tepat satu huruf dalam bahasa Inggris.

Contoh

Input: s = "Mississippi"c = "s"
Output: 4
Penjelasan: Mississippi memiliki s pada indeks 2, 3, 5, dan 6, jadi jawabannya adalah 4.

Input: s = "Banana"c = "b"
Output: 0
Penjelasan: Banana diawali dengan huruf kapital B, sedangkan kamu mencari huruf kecil b. Tidak ada yang cocok, jadi jawabannya adalah 0.

Pertanyaan lanjutan

Bagaimana jika c bisa berupa kata yang terdiri dari beberapa huruf, seperti ss? Apakah kecocokan yang tumpang tindih ikut dihitung, dan bagaimana perulanganmu berubah?

Petunjuk

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

0 dari 3 dibuka

Solusi

Setiap karakter dari s bisa berupa c, jadi periksa setiap karakter satu kali dan hitung kecocokannya. Perhatikan huruf besar-kecil: huruf kapital adalah karakter yang berbeda.

Hapus setiap c dan bandingkan panjangnya

Intuisi

Buat salinan s dengan menghapus setiap c. Setiap penghapusan membuat salinan lebih pendek satu karakter, jadi selisih panjangnya adalah jumlah karakter yang dihapus. Untuk Mississippi, salinannya adalah Miiippi: 11 dikurangi 7 sama dengan 4.

Waktunya O(n), tetapi salinan tersebut membutuhkan memori ekstra O(n) yang tidak diperlukan oleh penghitung.

Algoritma

Buat salinan s yang tidak menyertakan setiap karakter yang sama dengan c.
Ukur panjang s dan panjang salinannya.
Kembalikan panjang s dikurangi panjang salinannya.

def countChar(s, c):
    # Every c that disappears makes the string one character shorter.
    without = s.replace(c, "")
    return len(s) - len(without)

Satu iterasi dengan penghitung

Intuisi

Hitung saat kamu membaca, bukan dengan membuat salinan. Penghitung dimulai dari 0 dan bertambah 1 untuk setiap karakter yang sama dengan c. Kesamaan biasa mencegah huruf kapital cocok dengan huruf kecil.

Setiap karakter dibandingkan satu kali dan hanya penghitung yang disimpan: waktu O(n), ruang O(1). Tidak ada solusi yang lebih baik dari waktu O(n), karena karakter yang kamu lewati bisa jadi satu lagi c.

Algoritma

Baca huruf target dari c dan tetapkan count = 0.
Telusuri s satu karakter setiap kali.
Jika karakter tersebut sama dengan target, tambahkan 1 ke count.
Kembalikan count.

def countChar(s, c):
    count = 0
    for ch in s:
        if ch == c:
            count += 1
    return count

Jebakan dan kasus tepi

Mengabaikan kapitalisasi. Mengubah kedua sisi menjadi huruf kecil membuat Banana dengan b menghasilkan 1, padahal jawabannya 0.
Membandingkan karakter dengan string. Di Java, C, C++, C# dan Go, c berupa string, sedangkan s[i] atau s.charAt(i) adalah satu karakter. Ambil c[0] (atau c.charAt(0)) sekali sebelum perulangan.
Membandingkan string dengan == di Java. String.valueOf(s.charAt(i)) == c membandingkan identitas object dan hampir selalu menghasilkan false. Bandingkan nilai char.
Memanggil strlen(s) dalam kondisi perulangan di C. Fungsi ini memindai ulang string pada setiap langkah, sehingga 5 × 10^4 karakter membutuhkan sekitar 2.5 × 10^9 langkah.

Pertanyaan yang sering diajukan3

Bagaimana cara menghitung kemunculan sebuah karakter dalam string?

Telusuri string satu kali dengan penghitung yang dimulai dari 0, lalu tambahkan 1 setiap kali karakter saat ini sama dengan karakter yang kamu cari. Proses ini membutuhkan waktu O(n) dan memori tambahan O(1). Untuk menghitung tanpa membedakan huruf besar dan kecil, ubah string dan huruf menjadi huruf kecil terlebih dahulu.

Bisakah saya menggunakan fungsi count bawaan saat wawancara?

Biasanya ya, selama kamu bisa menjelaskan biaya komputasinya. str.count dan fungsi serupa di Python tetap membaca seluruh string, jadi kompleksitasnya O(n). Bersiaplah menulis perulangan jika pewawancara meminta.

Bagaimana cara menghitung semua karakter sekaligus?

Lakukan satu kali pemindaian dan catat jumlah kemunculan setiap karakter, dalam hash map atau array berisi 52 penghitung untuk huruf-huruf bahasa Inggris. Setelah pemindaian itu, jumlah kemunculan huruf apa pun dapat diketahui dengan satu kali pencarian. Gunakan cara ini saat kamu ditanya tentang banyak huruf dalam string yang sama.

def countChar(s, c):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

s = "Mississippi"
c = "s"

Output yang diharapkan