Letter Combinations of a Phone Number

Q: Berapa kompleksitas waktu untuk Kombinasi Huruf pada Nomor Telepon?

O(4^n · n) untuk n digit: ada 4^n string ketika setiap digit adalah 7 atau 9, dan masing-masing membutuhkan n langkah untuk ditulis. Itulah ukuran output, jadi tidak ada solusi yang lebih baik. Backtracking membutuhkan ruang tambahan O(n) selain output.

SedangBacktracking

+10

Pada keypad ponsel, setiap digit dari 2 hingga 9 memiliki beberapa huruf: 2 adalah abc, 3 adalah def, 4 adalah ghi, 5 adalah jkl, 6 adalah mno, 7 adalah pqrs, 8 adalah tuv, dan 9 adalah wxyz.

Kamu mendapatkan string digits. Pilih satu huruf untuk setiap digit, dengan mempertahankan urutan digit, maka kamu mendapatkan satu string yang dapat diketik menggunakan tombol tersebut. Kembalikan semua string tersebut, diurutkan berdasarkan urutan leksikografis (urutan kamus).

Fungsi

letterCombinations(digits: string) → string-array

digitsstring: digit yang ditekan, masing-masing dari 2 hingga 9
Mengembalikanstring-array: setiap string yang dapat diketik oleh tombol, dalam urutan leksikografis

Batasan

1 ≤ digits.length ≤ 4
Setiap karakter dalam digits adalah digit dari 2 hingga 9.
Jawabannya memuat paling banyak 4⁴ = 256 string.

Contoh

Input: digits = "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Penjelasan: 2 menawarkan a, b, c dan 3 menawarkan d, e, f. Setiap huruf pertama dipasangkan dengan setiap huruf kedua: 3 × 3 = 9 string, diurutkan dengan perubahan huruf pertama paling lambat.

Input: digits = "94"
Output: ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
Penjelasan: 9 memiliki empat huruf dan 4 memiliki tiga, jadi ada 4 × 3 = 12 string. Ketiga string yang dimulai dengan w muncul sebelum string pertama yang dimulai dengan x.

Pertanyaan lanjutan

Misalkan kamu hanya menginginkan kombinasi yang merupakan kata sungguhan dalam kamus. Bagaimana kamu menghindari membuat semua string 4^n terlebih dahulu?

Petunjuk

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

0 dari 3 dibuka

Solusi

Jawaban memuat hingga 4^n string, jadi setiap solusi memerlukan setidaknya sebanyak itu upaya untuk menuliskannya. Yang penting adalah menghasilkan setiap pilihan tepat satu kali, tanpa ada yang terlewat atau terulang. Inilah backtracking pada pohon keputusan dengan satu tingkat untuk setiap digit, dan setiap daun merupakan sebuah jawaban.

Susun string satu digit demi satu digit

Intuisi

Mulai dengan list yang berisi satu string kosong, lalu tambahkan satu digit setiap kali. Untuk "23", digit 2 mengubahnya menjadi a, b, c, lalu 3 memperluas masing-masing dengan d, e, dan f, sehingga menghasilkan sembilan string.

Urutannya tetap terurut. Jika list diurutkan sebelum sebuah digit, kamu memperluas prefiks sesuai urutan tersebut, dan setiap prefiks dengan huruf-huruf tombolnya dari kiri ke kanan: prefiks yang lebih awal tetap berada di urutan pertama, dan prefiks yang sama diurutkan berdasarkan huruf baru.

Jumlah pekerjaan sebanding dengan ukuran jawaban, tetapi saat kamu membangun satu tingkat, seluruh tingkat sebelumnya juga tetap tersimpan di memori.

Algoritma

Mulai dengan combos = [""], satu awalan kosong.
Untuk setiap digit, buat daftar baru: untuk setiap awalan dalam combos dan setiap huruf pada tombol digit tersebut, tambahkan prefix + letter.
Ganti combos dengan daftar baru.
Setelah digit terakhir, kembalikan combos.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    combos = [""]  # every prefix built so far; one empty prefix to start
    for digit in digits:
        # Each old prefix grows by each letter of this digit, in order.
        combos = [prefix + letter for prefix in combos for letter in KEYPAD[digit]]
    return combos

Melakukan backtracking pada pohon keputusan

Intuisi

Jawaban adalah daun-daun pada pohon keputusan. Akarnya adalah string kosong, dan setiap tingkat menambahkan satu huruf dari digit berikutnya: untuk "23", akar memiliki anak a, b, c, masing-masing memiliki anak untuk d, e, f.

Telusuri pohon itu secara mendalam dengan satu buffer, path. Pada tingkat i, pilih sebuah huruf dari digits[i] dengan menambahkannya, jelajahi dengan melakukan rekursi pada i+1, lalu urungkan dengan menghapusnya. Pengurungan ini memungkinkan satu buffer digunakan untuk seluruh pohon: setelah ad, ae, dan af, menghapus huruf terakhir mengembalikan path ke a, lalu ke string kosong, siap untuk b. Saat i mencapai akhir digits, simpan salinannya.

Waktunya tetap O(4^n · n), tetapi memori tambahan berupa buffer dan tumpukan pemanggilan, O(n).

Algoritma

Pertahankan path dan result tetap kosong.
Definisikan backtrack(i): jika i sama dengan panjang digits, simpan salinan path lalu kembalikan.
Jika tidak, untuk setiap huruf pada tombol digits[i], secara berurutan: tambahkan huruf itu ke path, panggil backtrack(i+1), lalu hapus huruf itu.
Panggil backtrack(0) lalu kembalikan result.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    result = []
    path = []  # the letters chosen so far, one per digit

    def backtrack(i):
        if i == len(digits):
            # Every digit has a letter: this leaf is one finished string.
            result.append("".join(path))
            return
        for letter in KEYPAD[digits[i]]:
            path.append(letter)   # choose
            backtrack(i + 1)      # explore the digits after this one
            path.pop()            # undo, so the next letter can take its place

    backtrack(0)
    return result

Jebakan dan kasus tepi

Menganggap setiap tombol memiliki tiga huruf. Mengambil tiga huruf mulai dari indeks (d-2)*3 pada alfabet menghilangkan s dari 7 dan membuat 8 dimulai dengan s. Tuliskan keypad sebagai tabel.
Lupa melakukan undo. path terus bertambah, dan jawaban kedua untuk "23" menjadi ade, bukan ae.
Menyimpan buffer alih-alih salinannya. Di Python, result.append(path) menyimpan list yang sama sebanyak sembilan kali, dan pada akhirnya list itu kosong.
Mencoba huruf tombol dari kanan ke kiri, atau menyusun string dari stack dalam versi iteratif. Keduanya merusak urutan terurut.
Di PHP dan R, "23" mungkin diterima sebagai angka 23. Ubah menjadi teks sebelum mengindeks karakternya.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk Kombinasi Huruf pada Nomor Telepon?

O(4^n · n) untuk n digit: ada 4^n string ketika setiap digit adalah 7 atau 9, dan masing-masing membutuhkan n langkah untuk ditulis. Itulah ukuran output, jadi tidak ada solusi yang lebih baik. Backtracking membutuhkan ruang tambahan O(n) selain output.

Mengapa backtracking mengembalikan kombinasi dalam urutan terurut?

Semua jawaban memiliki panjang yang sama, dan penelusuran mendalam menyelesaikan setiap string yang dimulai dengan a sebelum memilih b. Hal yang sama berlaku di setiap tingkat, selama huruf pada setiap kunci dicoba dari kiri ke kanan. Itulah urutan dictionary, jadi tidak perlu melakukan pengurutan.

Bagaimana dengan angka 0 dan 1?

Pada keypad ponsel, 0 dan 1 tidak memiliki huruf, dan versi ini hanya menggunakan 2 hingga 9. Jika angka tersebut bisa muncul, kamu harus menentukan apakah angka itu dilewati atau membuat jawabannya kosong. Dalam wawancara, tanyakan mana yang diinginkan.

def letterCombinations(digits):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

digits = "23"

Output yang diharapkan

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]