To Lower Case

Q: Mengapa selisih antara huruf besar dan huruf kecil adalah 32?

ASCII menempatkan huruf kapital pada kode 65 hingga 90 dan huruf kecil pada 97 hingga 122, dengan enam simbol di antaranya. Kedua alfabet memiliki urutan yang sama, jadi setiap pasangan berjarak 97 - 65 = 32 . 32 adalah satu bit, jadi mengatur bit itu mengubah huruf kapital menjadi huruf kecilnya.

Q: Bisakah kamu mengubah huruf besar-kecil dengan operasi bit?

Ya. Untuk huruf kapital, code | 32 mengatur bit yang membedakan kedua bentuk huruf dan menghasilkan huruf kecil, sedangkan code & ~32 menghapus bit itu lagi. Kamu tetap perlu memeriksa rentangnya terlebih dahulu, karena trik bit yang sama juga akan mengubah angka dan simbol.

Q: Berapa kompleksitas waktu untuk mengubah string menjadi huruf kecil?

Kompleksitasnya O(n) untuk string dengan panjang n , karena setiap karakter diperiksa satu kali. String baru membutuhkan ruang O(n) . Jika kamu bisa mengubah array karakter secara langsung, ruang tambahan berkurang menjadi O(1) .

PemulaArray dan string

+10

Kamu mendapatkan string s. Kembalikan string baru yang setiap huruf besar bahasa Inggrisnya, dari A hingga Z, diganti dengan huruf kecilnya. Setiap karakter lainnya, seperti huruf kecil, digit, atau simbol, tetap sama persis.

Fungsi

toLowerCase(s: string) → string

sstring: teks yang perlu dikonversi
Mengembalikanstring: s dengan setiap huruf besar diubah menjadi huruf kecil

Batasan

1 ≤ s.length ≤ 10⁴
Setiap karakter dari s adalah huruf bahasa Inggris, angka, atau salah satu simbol !#$%&()*+-./:;<=>?@[]^_`{|}~.

Contoh

Input: s = "Hello-World!"
Output: "hello-world!"
Penjelasan: Huruf kapital H dan W menjadi h dan w. - dan ! bukan huruf, jadi keduanya tetap di tempatnya.

Input: s = "coddy_2026"
Output: "coddy_2026"
Penjelasan: Tidak ada huruf kapital yang perlu diubah. Huruf kecil, _, dan digit tetap sama.

Pertanyaan lanjutan

Bisakah kamu menulis toUpperCase dengan perulangan yang sama, dan menjelaskan mengapa hanya satu bit kode karakter yang berbeda antara A dan a?

Petunjuk

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

0 dari 3 dibuka

Solusi

Setiap bahasa menyediakan fungsi lowercase, dan dalam kode produksi kamu harus memanggilnya. Pewawancara menanyakan soal ini untuk mengetahui apakah kamu tahu cara kerjanya: dalam ASCII, setiap huruf kapital memiliki kode yang tepat 32 lebih rendah daripada huruf kecilnya, jadi tambahkan 32 ke setiap kode antara 'A' dan 'Z'.

Memanggil fungsi lowercase bawaan

Intuisi

lower() milik Python, toLowerCase() milik JavaScript, downcase milik Ruby, dan fungsi serupa sudah melakukan tugas ini. C dan C++ menyediakan tolower untuk satu karakter, jadi kamu memanggilnya dalam perulangan. Setiap karakter diperiksa satu kali, dengan waktu O(n), dan string baru membutuhkan ruang O(n).

Beberapa fungsi ini mengikuti pengaturan bahasa mesin. Dalam bahasa Turki, huruf kecil dari I adalah ı tanpa titik, jadi versi Java dan C# meminta aturan tetap dengan Locale.ROOT dan ToLowerInvariant. Dalam wawancara, jawaban ini sering tidak diterima karena menyembunyikan gagasan yang menjadi inti pertanyaan.

Algoritma

Panggil fungsi lowercase dalam bahasa pemrogramanmu pada s, atau panggil tolower pada setiap karakter dalam C dan C++.
Minta aturan tetap yang tidak bergantung pada bahasa jika fungsi tersebut menyediakan pilihan itu.
Kembalikan hasilnya.

def toLowerCase(s):
    return s.lower()

Geser kode karakter huruf kapital

Intuisi

Setiap karakter disimpan sebagai angka. Dalam ASCII, A hingga Z memiliki kode 65 hingga 90 dan a hingga z memiliki kode 97 hingga 122. Kedua rentang berurutan secara alfabetis dan berjarak 32, jadi huruf kecil dari huruf kapital mana pun memiliki kode sebesar kodenya ditambah 32: H adalah 72 dan h adalah 104. Hanya kode 65 hingga 90 yang berubah; simbol seperti _ berada di antara Z dan a dan harus disalin apa adanya.

Setiap karakter diperiksa satu kali, dengan waktu O(n), dan hasilnya adalah string baru dengan panjang yang sama, dengan ruang O(n). Menulis 'a' - 'A' alih-alih 32 menunjukkan asal angka tersebut.

Algoritma

Salin s ke dalam array karakter atau kode.
Untuk setiap posisi, baca kode karakternya.
Jika kodenya berada di antara 'A' (65) dan 'Z' (90), tambahkan 32.
Ubah array kembali menjadi string dan kembalikan hasilnya.

def toLowerCase(s):
    # Every capital letter sits 32 codes below its small letter: 'A' is 65, 'a' is 97.
    shift = ord("a") - ord("A")
    chars = []
    for ch in s:
        if "A" <= ch <= "Z":
            ch = chr(ord(ch) + shift)
        chars.append(ch)
    return "".join(chars)

Jebakan dan kasus tepi

Menambahkan 32 ke setiap karakter yang bukan huruf kecil. Digit dan simbol juga berubah: 1 menjadi Q.
Hanya memeriksa satu ujung rentang. code < 'a' juga mencakup [, _, dan @, sedangkan code >= 'A' juga mencakup setiap huruf kecil.
Menggunakan < alih-alih <= di ujung rentang, sehingga A atau Z tetap huruf besar.
Menyusun jawaban dengan result = result + ch pada string yang immutable. Setiap langkah menyalin semua isi sejauh ini, sehingga prosesnya kuadratik untuk n = 10^4.
Dalam C, menulis ke input atau lupa menambahkan '\0' sebagai penanda akhir. Alokasikan n + 1 byte untuk salinannya.

Pertanyaan yang sering diajukan3

Mengapa selisih antara huruf besar dan huruf kecil adalah 32?

ASCII menempatkan huruf kapital pada kode 65 hingga 90 dan huruf kecil pada 97 hingga 122, dengan enam simbol di antaranya. Kedua alfabet memiliki urutan yang sama, jadi setiap pasangan berjarak 97 - 65 = 32. 32 adalah satu bit, jadi mengatur bit itu mengubah huruf kapital menjadi huruf kecilnya.

Bisakah kamu mengubah huruf besar-kecil dengan operasi bit?

Ya. Untuk huruf kapital, code | 32 mengatur bit yang membedakan kedua bentuk huruf dan menghasilkan huruf kecil, sedangkan code & ~32 menghapus bit itu lagi. Kamu tetap perlu memeriksa rentangnya terlebih dahulu, karena trik bit yang sama juga akan mengubah angka dan simbol.

Berapa kompleksitas waktu untuk mengubah string menjadi huruf kecil?

Kompleksitasnya O(n) untuk string dengan panjang n, karena setiap karakter diperiksa satu kali. String baru membutuhkan ruang O(n). Jika kamu bisa mengubah array karakter secara langsung, ruang tambahan berkurang menjadi O(1).

def toLowerCase(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "Hello-World!"

Output yang diharapkan

"hello-world!"