Word Break

Q: Berapa kompleksitas waktu Word Break?

Tabel bottom-up dengan hash set berjalan dalam O(m × L + n × L²) , dengan n sebagai panjang s , m sebagai jumlah kata, dan L sebagai panjang kata terpanjang. Membandingkan setiap kata di setiap posisi membutuhkan biaya O(n × m × L) . Rekursi biasa memiliki kompleksitas eksponensial.

Q: Apakah Word Break merupakan masalah pemrograman dinamis atau masalah graf?

Keduanya. Sebagai pemrograman dinamis, canEnd[i] menyatakan apakah i huruf pertama dapat dipisah. Sebagai graf, setiap indeks adalah node, dengan edge dari i ke j ketika huruf-huruf di antaranya membentuk sebuah kata, dan kamu mencari tahu apakah n dapat dicapai dari 0. Penelusuran breadth-first melakukan pekerjaan yang sama seperti tabel.

SedangDynamic programming Hashing

+10

Kamu mendapat sebuah string s dan sebuah list kata wordDict. Kembalikan true jika kamu dapat membagi s menjadi beberapa bagian yang semuanya merupakan kata dari wordDict, dan false jika tidak.

Bagian-bagian tersebut tetap berurutan dan secara keseluruhan menggunakan setiap huruf dalam s tepat satu kali. Sebuah kata dapat digunakan berapa kali pun, dan kamu tidak harus menggunakan setiap kata.

Fungsi

wordBreak(s: string, wordDict: string-array) → boolean

sstring: string yang akan dipotong menjadi kata-kata
wordDictstring-array: kata-kata yang boleh kamu gunakan, sebanyak yang kamu mau
Mengembalikanboolean: true jika s dapat dipisah menjadi kata-kata dalam dictionary, false jika tidak

Batasan

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
s dan setiap kata hanya terdiri dari huruf kecil bahasa Inggris.
Kata-kata dalam wordDict semuanya berbeda.

Contoh

Input: s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
Output: true
Penjelasan: Pisahkan menjadi sun, flower, seed. Mengambil flow setelah sun menyisakan er, yang tidak menjadi awalan kata apa pun, jadi kata pertama yang cocok belum tentu selalu tepat.

Input: s = "bananaban"wordDict = ["ban", "ana"]
Output: true
Penjelasan: ban + ana + ban mencakup string tersebut dan menggunakan ban dua kali, hal ini diperbolehkan.

Input: s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
Output: false
Penjelasan: pine + apple dan pineapple sama-sama menyisakan tart. Hanya tar yang cocok di sana, sehingga tersisa t sendirian, jadi tidak ada pemotongan yang berhasil.

Pertanyaan lanjutan

Kembalikan jumlah kata paling sedikit yang dapat digunakan oleh cut yang valid, atau -1 jika s tidak dapat dipotong. Apa yang berubah pada tabel, dan apakah waktu eksekusinya berubah?

Petunjuk

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

0 dari 3 dibuka

Solusi

Memproses satu kata setiap kali tidak berhasil, dan mencoba setiap pemotongan membutuhkan waktu eksponensial. Namun, apakah sisa s bisa dipotong hanya bergantung pada titik awalnya, jadi hanya ada n + 1 pertanyaan. Di bawah ini, n adalah panjang s, m adalah jumlah kata, dan L adalah panjang kata terpanjang.

Coba setiap kata di setiap posisi

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Potongan pertama harus berupa kata yang diawali s. Coba setiap kata seperti itu, lalu ajukan pertanyaan yang sama tentang huruf-huruf yang tersisa; sisa yang kosong berarti setiap huruf sudah dipotong. Mencoba setiap kata pertama, lalu setiap kata kedua, tidak mungkin melewatkan pemotongan yang valid.

Proses ini memeriksa sisa yang sama berulang kali. Dengan 299 salinan a yang diikuti satu b, dan kata-kata a, aa hingga sepuluh a, lebih dari 10^89 cara untuk memotong a menjadi beberapa blok akan mencapai b dan gagal, dan rekursi mencoba semuanya.

Algoritma

Tulis canSplit(start): apakah huruf dari start hingga akhir bisa dipisahkan? Jika start sama dengan panjang s, kembalikan true.
Untuk setiap kata yang terkandung dalam s pada indeks start, jika canSplit(start + its length) bernilai true, kembalikan true.
Jika tidak, kembalikan false. Jawabannya adalah canSplit(0).

def wordBreak(s, wordDict):
    def can_split(start):
        # Can s[start:] be cut into dictionary words?
        if start == len(s):
            return True  # nothing left to cut
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                return True
        return False

    return can_split(0)

Rekursi dengan memo

Intuisi

Jawaban untuk sisa hanya bergantung pada start, yang memiliki n + 1 nilai. Dalam contoh a, sisa pada indeks 20 dicapai setelah dua blok berisi sepuluh, setelah dua puluh a tunggal, dan dengan banyak cara lainnya, dan hasilnya false setiap kali. Simpan jawaban untuk setiap nilai start sekali, lalu gunakan kembali.

Memo harus menyimpan jawaban false. Nilai true langsung mengakhiri seluruh pencarian, jadi semua pekerjaan berulang terjadi pada cabang yang gagal.

Setiap nilai start mencoba setiap kata, dengan membandingkan hingga L huruf: waktu O(n × m × L), paling banyak 6 × 10^6 pemeriksaan huruf, dan ruang O(n).

Algoritma

Buat memo dengan satu slot untuk setiap indeks, masing-masing ditandai sebagai belum dihitung.
Di canSplit(start), kembalikan true saat mencapai akhir s, atau jawaban yang tersimpan jika slot tersebut berisi jawaban.
Jika tidak, coba setiap kata seperti dalam rekursi biasa, simpan hasilnya di slot, termasuk false, lalu kembalikan hasil tersebut.

def wordBreak(s, wordDict):
    memo = [None] * len(s)  # memo[start]: answer for s[start:], None until worked out

    def can_split(start):
        if start == len(s):
            return True
        if memo[start] is not None:
            return memo[start]
        result = False
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                result = True
                break
        memo[start] = result
        return result

    return can_split(0)

Dari bawah ke atas untuk prefiks dengan hash set

Intuisi

Kerjakan pada prefiks. Biarkan canEnd[i] menunjukkan apakah i huruf pertama dapat dipotong; canEnd[0] adalah true, karena prefiks kosong tidak memerlukan kata. end huruf pertama dapat dipotong tepat ketika potongan terakhirnya, dari start sampai end, adalah sebuah kata dan canEnd[start] adalah true. Karena diisi dari kiri ke kanan, setiap canEnd[start] yang kamu perlukan sudah diketahui.

Masukkan kata-katanya ke dalam hash set. Tidak ada kata yang lebih panjang dari L, jadi hanya L potongan yang berakhir di end yang mungkin cocok, sebesar apa pun dictionary-nya. Pada sunflowerseed, canEnd bernilai true pada 0, 3, 7, 9, dan 13; jalan buntu di 7 tidak menimbulkan masalah.

Setiap posisi dari n posisi mencari paling banyak L potongan, dan setiap potongan memerlukan hingga L langkah untuk dibuat dan di-hash: O(n × L²), paling banyak 1.2 × 10^5 langkah, ditambah O(m × L) untuk set.

Algoritma

Masukkan kata-kata ke dalam hash set, lalu catat panjang terbesarnya, L.
Buat canEnd dengan n + 1 entri, semuanya false, lalu atur canEnd[0] menjadi true.
Untuk setiap end dari 1 hingga n dan setiap length dari 1 hingga min(L, end): jika canEnd[end-length] bernilai true dan potongan dengan panjang tersebut yang berakhir di end ada di dalam set, atur canEnd[end] menjadi true lalu berhenti.
Kembalikan canEnd[n].

def wordBreak(s, wordDict):
    words = set(wordDict)
    longest = max(len(word) for word in wordDict)
    n = len(s)
    # can_end[i]: the first i letters split into dictionary words
    can_end = [False] * (n + 1)
    can_end[0] = True  # the empty prefix needs no words
    for end in range(1, n + 1):
        # The last word is s[end-length:end], and no word is longer than longest.
        for length in range(1, min(longest, end) + 1):
            if can_end[end - length] and s[end - length:end] in words:
                can_end[end] = True
                break
    return can_end[n]

Jebakan dan kasus tepi

Memotong secara rakus. Memotong bagian terpanjang terlebih dahulu menghasilkan carpet dari carpetal dan menyisakan al, padahal car + petal bisa digunakan; memotong bagian terpendek terlebih dahulu membuat proses terhenti pada sunflowerseed.
Hanya menyimpan jawaban true di memo. Pekerjaan yang berulang terjadi pada cabang false, sehingga contoh dengan huruf a tetap membutuhkan waktu eksponensial.
Membuat tabel dengan satu entri terlalu sedikit. canEnd memerlukan n + 1 entri untuk panjang prefiks 0 hingga n.
Membandingkan melewati akhir s, misalnya kata abc dengan sisa ab. Periksa panjangnya terlebih dahulu.
Di Lua dan R, posisi string dimulai dari 1: potongan sepanjang k yang berakhir pada huruf e dimulai pada e-k+1.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Word Break?

Tabel bottom-up dengan hash set berjalan dalam O(m × L + n × L²), dengan n sebagai panjang s, m sebagai jumlah kata, dan L sebagai panjang kata terpanjang. Membandingkan setiap kata di setiap posisi membutuhkan biaya O(n × m × L). Rekursi biasa memiliki kompleksitas eksponensial.

Apakah Word Break merupakan masalah pemrograman dinamis atau masalah graf?

Keduanya. Sebagai pemrograman dinamis, canEnd[i] menyatakan apakah i huruf pertama dapat dipisah. Sebagai graf, setiap indeks adalah node, dengan edge dari i ke j ketika huruf-huruf di antaranya membentuk sebuah kata, dan kamu mencari tahu apakah n dapat dicapai dari 0. Penelusuran breadth-first melakukan pekerjaan yang sama seperti tabel.

Bagaimana cara menampilkan setiap kalimat alih-alih mengembalikan true atau false?

Backtrack: pada setiap indeks, coba setiap kata yang cocok, lakukan rekursi pada sisanya, dan ingat daftar kalimat untuk setiap indeks. Jalankan tabel true atau false terlebih dahulu, supaya string yang tidak bisa dipotong dapat melewati pencarian. Jumlah kalimat dapat bertambah secara eksponensial, sehingga ukuran output menentukan waktu eksekusi.

def wordBreak(s, wordDict):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "sunflowerseed"
wordDict = ["sun", "flow", "flower", "seed"]

Output yang diharapkan

true

Word Break

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Coba setiap kata di setiap posisi

Rekursi dengan memo

Dari bawah ke atas untuk prefiks dengan hash set

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa