Generate Parentheses

Q: Apa kompleksitas waktu dari Generate Parentheses?

Backtracking menghasilkan C(n) = (2n)! / ((n+1)! n!) string, yaitu bilangan Catalan, yang tumbuh seperti 4^n / (n^1.5 √π) . Masing-masing membutuhkan waktu O(n) untuk dibuat dan disalin, sehingga kompleksitas waktunya adalah O(4^n / √n) . Ruang ekstra adalah O(n) untuk string saat ini dan tumpukan pemanggilan, ditambah output.

Q: Berapa banyak string tanda kurung yang valid untuk n pasang?

Bilangan Catalan ke-n: 1, 2, 5, 14, 42, 132, 429, dan 1,430 untuk n dari 1 hingga 8. Setiap string yang terbentuk dengan benar terbagi menjadi ( A ) B, dengan ) yang cocok dengan ( pertama, serta A dan B memiliki n - 1 pasang. Menjumlahkan berdasarkan ukuran A menghasilkan relasi rekurensi Catalan.

Q: Bisakah Generate Parentheses diselesaikan tanpa rekursi?

Ya. Simpan tumpukan state parsial, masing-masing berupa string dengan dua penghitungnya, lalu kembangkan setiap state dengan dua aturan yang sama. Push pengembangan ) sebelum pengembangan ( , sehingga pengembangan ( diambil lebih dulu dan output tetap terurut.

SedangBacktracking Rekursi

+10

Rangkaian tanda kurung terbentuk dengan baik jika, saat dibaca dari kiri ke kanan, jumlah ) tidak pernah melebihi jumlah (, dan kedua jumlah tersebut sama pada akhirnya. Jadi, (())() terbentuk dengan baik, sedangkan ())( tidak: karakter ketiganya menutup pasangan yang tidak pernah dibuka.

Diberikan bilangan bulat n, kembalikan semua string yang terbentuk dengan baik, dengan n tanda kurung buka dan n tanda kurung tutup, diurutkan secara leksikografis, dengan ( berada sebelum ).

Fungsi

generateParenthesis(n: integer) → string-array

ninteger: jumlah pasangan tanda kurung
Mengembalikanstring-array: setiap string valid yang terdiri atas n pasang, dalam urutan leksikografis

Batasan

1 ≤ n ≤ 8
Untuk n = 8, jawabannya memuat 1,430 string.

Contoh

Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Penjelasan: Tiga pasang kurung menghasilkan lima string yang valid. ((())) membuka ketiganya terlebih dahulu, jadi urutannya berada di awal; ()()() langsung menutup setiap pasangan dan berada di akhir.

Input: n = 1
Output: ["()"]
Penjelasan: Satu pasangan memiliki string yang tersusun dengan benar. Susunan lainnya, )(, menutup sebelum apa pun dibuka.

Pertanyaan lanjutan

Bisakah kamu menghitung string yang terbentuk dengan benar untuk n pasang tanpa membuatnya?

Petunjuk

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

0 dari 3 dibuka

Solusi

Hanya sedikit string dengan panjang 2n yang terbentuk dengan benar: 1.430 dari 65.536 untuk n = 8. Bangun setiap string dari kiri ke kanan dan tambahkan karakter hanya jika prefiksnya masih bisa dilengkapi. Dua pencacah menentukan hal itu, dan mencoba ( sebelum ) membuat string tersusun terurut.

Susun setiap string, lalu periksa

Intuisi

Isi 2n posisi dengan setiap kombinasi ( dan ), sebanyak 4^n string, lalu pertahankan string yang terbentuk dengan benar. Untuk memeriksa sebuah string, telusuri dengan nilai keseimbangan: tambah 1 untuk (, kurangi 1 untuk ). String terbentuk dengan benar jika nilainya tidak pernah kurang dari 0 dan berakhir di 0. Menempatkan ( sebelum ) di setiap posisi akan mengurutkan string.

Setiap string memerlukan O(n) untuk diperiksa. Untuk n = 8, ada 65,536 string untuk 1,430 jawaban, sehingga sekitar 98% pekerjaan terbuang, dan jumlahnya bertambah empat kali lipat untuk setiap pasangan tambahan.

Algoritma

Simpan buffer berisi 2n karakter dan list untuk jawaban.
fill(pos): jika pos sama dengan 2n, simpan buffer jika susunannya valid.
Jika tidak, letakkan ( pada pos dan panggil fill(pos + 1), lalu letakkan ) di sana dan panggil lagi.
Untuk memeriksa, tambahkan 1 untuk setiap ( dan kurangi 1 untuk setiap ). Tolak jika keseimbangannya kurang dari 0 atau tidak berakhir di 0.
Panggil fill(0) dan kembalikan string yang tersimpan.

def generateParenthesis(n):
    result = []
    path = []

    def is_balanced(text):
        balance = 0
        for ch in text:
            balance += 1 if ch == "(" else -1
            if balance < 0:
                return False  # a ")" with nothing open to close
        return balance == 0

    def fill():
        if len(path) == 2 * n:
            text = "".join(path)
            if is_balanced(text):
                result.append(text)
            return
        for ch in "()":  # "(" first keeps the output sorted
            path.append(ch)
            fill()
            path.pop()

    fill()
    return result

Telusuri kembali jumlah tanda kurung buka dan tutup

Intuisi

Pindahkan pemeriksaan ke dalam proses pembangunan. Sebuah prefiks dapat berkembang menjadi string yang terbentuk dengan benar jika menggunakan paling banyak n ( dan jumlah ) tidak pernah lebih banyak daripada jumlah (. Jadi, ( diizinkan selama opened < n, dan ) diizinkan selama closed < opened. Pada panjang 2n, kedua jumlah bernilai n, dan string terbentuk dengan benar tanpa ada yang perlu diperiksa lagi.

Tidak ada jawaban yang terlewat, karena setiap prefiks dari string yang terbentuk dengan benar mengikuti kedua aturan tersebut. Tidak ada cabang yang sia-sia: untuk n = 2, cabang (( hanya bisa ditutup dua kali, sehingga menghasilkan (()), dan cabang () hanya bisa membuka dan menutup, sehingga menghasilkan ()(). Setiap string merupakan satu jalur melalui pohon, jadi string tersebut muncul sekali, dan cabang ( dijelajahi lebih dahulu, sehingga output terurut.

Setiap daun adalah jawaban, jadi usaha yang diperlukan sebanding dengan output: O(4^n / √n).

Algoritma

Pertahankan string yang sedang dibuat dan dua penghitung, opened dan closed, yang keduanya bernilai 0.
Jika panjang string adalah 2n, simpan salinannya dan kembalikan.
Jika opened < n, tambahkan (, lakukan rekursi dengan opened + 1, lalu hapus karakter tersebut.
Jika closed < opened, tambahkan ), lakukan rekursi dengan closed + 1, lalu hapus karakter tersebut.
Mulai dari string kosong dan kembalikan string yang tersimpan.

def generateParenthesis(n):
    result = []
    path = []

    def backtrack(opened, closed):
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        # "(" sorts before ")", so trying it first keeps the output sorted
        if opened < n:
            path.append("(")
            backtrack(opened + 1, closed)
            path.pop()
        if closed < opened:  # only close a pair that is open
            path.append(")")
            backtrack(opened, closed + 1)
            path.pop()

    backtrack(0, 0)
    return result

Jebakan dan kasus tepi

Mengizinkan ) saat closed < n, bukan saat closed < opened. Ini membentuk ())(, yang menutup pasangan yang belum pernah dibuka.
Hanya memeriksa apakah jumlahnya sama di akhir. Ini menerima )(; keseimbangannya harus tetap 0 atau lebih di setiap langkah.
Mencoba ) sebelum (. String yang benar muncul dalam urutan terbalik.
Menyimpan buffer bersama, bukan salinannya, saat list atau string builder dapat diubah. Setiap jawaban yang disimpan kemudian menampilkan buffer yang sama, yang dikosongkan lagi oleh backtracking.
Menentukan ukuran array hasil tetap berdasarkan perkiraan kecil. n = 8 memiliki 1,430 jawaban.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Generate Parentheses?

Backtracking menghasilkan C(n) = (2n)! / ((n+1)! n!) string, yaitu bilangan Catalan, yang tumbuh seperti 4^n / (n^1.5 √π). Masing-masing membutuhkan waktu O(n) untuk dibuat dan disalin, sehingga kompleksitas waktunya adalah O(4^n / √n). Ruang ekstra adalah O(n) untuk string saat ini dan tumpukan pemanggilan, ditambah output.

Berapa banyak string tanda kurung yang valid untuk n pasang?

Bilangan Catalan ke-n: 1, 2, 5, 14, 42, 132, 429, dan 1,430 untuk n dari 1 hingga 8. Setiap string yang terbentuk dengan benar terbagi menjadi ( A ) B, dengan ) yang cocok dengan ( pertama, serta A dan B memiliki n - 1 pasang. Menjumlahkan berdasarkan ukuran A menghasilkan relasi rekurensi Catalan.

Bisakah Generate Parentheses diselesaikan tanpa rekursi?

Ya. Simpan tumpukan state parsial, masing-masing berupa string dengan dua penghitungnya, lalu kembangkan setiap state dengan dua aturan yang sama. Push pengembangan ) sebelum pengembangan (, sehingga pengembangan ( diambil lebih dulu dan output tetap terurut.

def generateParenthesis(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

n = 3

Output yang diharapkan

["((()))", "(()())", "(())()", "()(())", "()()()"]