Decode Ways
Pesan yang terdiri dari huruf kapital dikodekan dengan A = 1, B = 2, dan seterusnya hingga Z = 26, lalu kode-kode tersebut ditulis tanpa pemisah. Diberikan string digit s, kembalikan jumlah pesan yang mungkin menghasilkan string tersebut.
Satu huruf dibaca dari satu digit atau dua digit berurutan, dan kode tidak pernah dimulai dengan 0: 06 bukan 6, dan 0 saja bukan huruf. Jika tidak ada pembacaan yang berhasil, kembalikan 0.
Fungsi
- sstring
- string digit yang akan didekode
- Mengembalikaninteger
- jumlah pesan berupa huruf yang dikodekan menjadi s
Batasan
1 ≤ s.length ≤ 100shanya berisi digit0sampai9, dan bisa diawali dengan0.- Setiap prefiks dan sufiks
smemiliki kurang dari231kemungkinan pembacaan, sehingga jawabannya dan setiap hitungan yang kamu peroleh sepanjang proses muat dalam bilangan bulat 32-bit bertanda.
Contoh
- Input
- s = "2611"
- Output
- 4
- Penjelasan
- Keempat pembacaannya adalah
2 6 1 1(BFAA),26 1 1(ZAA),2 6 11(BFK), dan26 11(ZK). Digit tengah tidak pernah berpasangan karena 61 lebih besar daripada 26.
- Input
- s = "1203"
- Output
- 1
- Penjelasan
0harus dipasangkan dengan2sebelumnya menjadi20, yang menghasilkan1 20 3(ATC). Membaca12terlebih dahulu akan membuat0tersisa sendiri, dan03dimulai dengan 0.
- Input
- s = "06"
- Output
- 0
- Penjelasan
- Huruf pertama harus dimulai dengan
0.0saja bukan huruf dan06bukan kode, jadi tidak ada pesan yang menghasilkan string ini.
Pertanyaan lanjutan
Bagaimana jika s juga dapat berisi *, yang mewakili digit apa pun dari 1 hingga 9? Bisakah kamu menghitung kemungkinan pembacaan dalam waktu O(n), modulo 10^9+7?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Perhatikan hanya digit pertama. Dalam berapa cara huruf pertama dapat dibaca, dan apa yang tersisa dari string setelah setiap pilihan?
Jumlah pembacaan sisa string hanya bergantung pada titik awal sisa tersebut, bukan pada cara kamu mencapainya. Hitung setiap titik awal satu kali, lalu gunakan kembali hitungannya.
Misalkan
ways(i)menghitung cara membacaidigit pertama, denganways(0) = 1. Tambahkanways(i-1)jika digiti-1bukan0, dan tambahkanways(i-2)jika dua digit sebelum posisiimembentuk angka dari 10 hingga 26. Kamu hanya memerlukan dua hitungan terakhir.
Solusi
Setiap digit bisa menjadi huruf sendiri atau bergabung dengan digit di sebelahnya, sehingga jumlah cara membacanya bertumbuh seperti bilangan Fibonacci: 45 angka satu memiliki 1836311903 cara. Mustahil mencantumkan semuanya, tetapi cara menyelesaikan pembacaan hanya bergantung pada posisi yang dicapai, sehingga setiap posisi hanya perlu dihitung sekali. 0 hanya bisa mengakhiri 10 atau 20.
Coba kedua cara membaca dengan rekursi
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Pada indeks i, digit 0 tidak memulai huruf apa pun, sehingga jalur itu tidak menghasilkan pembacaan. Jika tidak, baca satu digit dan hitung jumlah cara membaca sisanya mulai dari i+1; jika kedua digit membentuk angka dari 10 sampai 26, baca keduanya juga dan hitung jumlah cara membaca sisanya mulai dari i+2. Kedua pilihan menghasilkan huruf pertama yang berbeda, jadi jumlah caranya bisa dijumlahkan tanpa tumpang tindih. Mencapai akhir berarti satu pembacaan selesai.
Tidak ada yang diingat, jadi pemanggilannya mengikuti aturan Fibonacci: 45 digit satu membutuhkan sekitar 5 × 10^9 pemanggilan. Jawaban 0 tidak lebih cepat: 44 digit satu, 55 digit tiga, dan satu digit 0 di akhir membutuhkan sekitar 10^11 pemanggilan, karena setiap pembacaan digit satu baru gagal pada digit terakhir.
Algoritma
waysFrom(i)menghitung cara membaca digit mulai dari indeksi.- Di akhir string, kembalikan 1. Jika menemukan
0, kembalikan 0. - Jika tidak, kembalikan
waysFrom(i+1), ditambahwaysFrom(i+2)jika digitidani+1membentuk angka paling banyak 26. - Jawabannya adalah
waysFrom(0).
def numDecodings(s):
n = len(s)
def ways_from(i):
# The number of ways to decode s[i:].
if i == n:
return 1 # nothing left: one finished reading
if s[i] == "0":
return 0 # no letter code starts with 0
ways = ways_from(i + 1) # read one digit
if i + 1 < n and int(s[i:i + 2]) <= 26:
ways += ways_from(i + 2) # read two digits, 10 to 26
return ways
return ways_from(0)Rekursi dengan memo
Intuisi
Rekursi mengajukan pertanyaan yang sama berkali-kali. Dalam "11111", hitungan dari indeks 3 diperlukan setelah 1 1 1, setelah 11 1, dan setelah 1 11, dan hitungannya sama setiap kali karena hanya bergantung pada digit mulai dari indeks 3. Simpan setiap hitungan saat pertama kali kamu menghitungnya, dan tandai slot yang belum dihitung dengan -1, karena 0 adalah hitungan yang valid.
Ada n posisi, masing-masing dihitung sekali dengan pekerjaan konstan: waktu O(n). Memo dan tumpukan pemanggilan membutuhkan ruang O(n), dengan kedalaman paling banyak 100 pemanggilan.
Algoritma
- Isi
memodengan-1, satu slot untuk setiap indeks. - Di
waysFrom(i), kembalikan 1 di akhir string danmemo[i]jika nilainya bukan-1. - Jika tidak, hitung seperti pada rekursi biasa, simpan hitungannya di
memo[i], termasuk nilai nol, lalu kembalikan nilainya.
def numDecodings(s):
n = len(s)
memo = [-1] * n # memo[i]: ways to decode s[i:], -1 until worked out
def ways_from(i):
if i == n:
return 1
if memo[i] != -1:
return memo[i]
ways = 0
if s[i] != "0":
ways = ways_from(i + 1) # read one digit
if i + 1 < n and int(s[i:i + 2]) <= 26:
ways += ways_from(i + 2) # read two digits, 10 to 26
memo[i] = ways
return ways
return ways_from(0)Bottom-up dengan dua pencacah
Intuisi
Hitung prefiks saja. Misalkan ways(i) adalah jumlah cara membaca i digit pertama. Huruf terakhir bisa berupa digit i-1 saja, yang harus bernilai 1 hingga 9 dan menyisakan ways(i-1) cara membaca, atau digit i-2 dan i-1 secara bersamaan, yang harus membentuk angka 10 hingga 26 dan menyisakan ways(i-2). Jumlahkan bagian yang kondisinya terpenuhi. Prefiks kosong memiliki satu cara membaca, jadi ways(0) = 1.
Untuk "1203", jumlahnya menjadi 1, 2, lalu kembali menjadi 1 pada 0, karena hanya 20 yang bisa digunakan dan jumlahnya kembali ke nilai sebelum 2. 3 berdiri sendiri, jadi jumlahnya tetap 1. Setiap jumlah melihat dua posisi sebelumnya, jadi dua variabel menggantikan tabel: waktu O(n), ruang O(1).
Algoritma
- Tetapkan
twoBack = 0danoneBack = 1, jumlah untuk prefiks kosong. - Untuk setiap indeks
i, tetapkancurrentkeoneBackjika digitibukan0, jika tidak, tetapkan ke 0. - Jika
i ≥ 1, digiti-1bukan0, dan digiti-1sertaimembentuk bilangan paling banyak 26, tambahkantwoBack. - Geser:
twoBack = oneBack, laluoneBack = current. - Kembalikan
oneBack.
def numDecodings(s):
# ways(i) counts the readings of the first i digits; ways(0) = 1.
two_back, one_back = 0, 1 # ways(i-1) and ways(i) before digit i is read
for i in range(len(s)):
current = 0
if s[i] != "0":
current = one_back # digit i is a letter on its own
if i >= 1 and s[i - 1] != "0" and int(s[i - 1:i + 1]) <= 26:
current += two_back # digits i-1 and i form one letter, 10 to 26
two_back, one_back = one_back, current
return one_back
Jebakan dan kasus tepi
- Menganggap
0sebagai huruf, atau06sebagai 6."30","100", dan"06"semuanya memiliki 0 cara membaca. - Menguji potongan dua digit hanya dengan
≤ 26.05bernilai 5 sebagai angka, tetapi bukan kode, jadi periksa bahwa digit pertamanya bukan0. - Menandai slot memo yang belum diketahui dengan 0. Posisi dengan 0 cara membaca kemudian tidak pernah dianggap tersimpan: untuk 44 angka satu, 55 angka tiga, dan
0terakhir, jumlah pemanggilan kembali menjadi sekitar10^11. - Membaca digit sebelum indeks 0. Batasi pemeriksaan dua digit dengan
i ≥ 1; di Python,s[-1]diam-diam membaca digit terakhir. - Mengubah
smenjadi satu angka. Seratus digit tidak muat dalam tipe integer apa pun, dan nol di depan yang mengubah jawabannya akan hilang.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu Decode Ways?
Solusi bottom-up membaca setiap digit satu kali dengan pekerjaan konstan: waktu O(n) dan ruang ekstra O(1). Rekursi dengan memoization juga membutuhkan waktu O(n), tetapi menggunakan ruang O(n). Rekursi biasa bersifat eksponensial: pada string yang terdiri dari angka satu, jumlah pemanggilan bertambah seperti 1.618^n.
Bagaimana hubungan Decode Ways dengan Climbing Stairs?
Keduanya menghitung cara untuk menutupi sebuah garis dengan langkah berukuran 1 dan 2. Dalam Climbing Stairs, setiap langkah diperbolehkan, sehingga jumlahnya adalah bilangan Fibonacci. Dalam Decode Ways, langkah satu digit memerlukan angka 1 hingga 9 dan langkah dua digit memerlukan angka 10 hingga 26, sehingga setiap suku hanya ditambahkan ketika kondisinya terpenuhi.
Bagaimana cara menangani angka nol dalam Decode Ways?
0 tidak pernah menjadi huruf dengan sendirinya, jadi angka ini harus dipasangkan dengan digit sebelumnya, seperti 10 atau 20. Angka ini menambahkan jumlah dari dua digit sebelumnya hanya setelah 1 atau 2, dan tidak menambahkan apa pun jika tidak. 0 di awal, dua angka nol berturut-turut, atau 0 setelah 3 hingga 9 menghasilkan 0.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def numDecodings(s):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
s = "2611"
Output yang diharapkan
4