Meditasi LeetCode: Pecah Kata

Penerangan untuk masalah ini ialah:

Memandangkan rentetan s dan kamus rentetan wordDict, kembalikan benar jika s boleh dibahagikan kepada urutan yang dipisahkan ruang bagi satu atau lebih perkataan kamus.

Perhatikan bahawa perkataan yang sama dalam kamus boleh digunakan semula beberapa kali dalam pembahagian.

Contohnya:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true

Explanation: Return true because "leetcode" can be segmented as "leet code".

Atau:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Atau:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Selain itu, kekangan kami menunjukkan bahawa semua rentetan wordDict adalah **unik**, dan:

• 1 <= s.panjang <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].panjang <= 20
• s dan wordDict[i] hanya terdiri daripada huruf kecil Inggeris.

---

Melanjutkan dengan penyelesaian pengaturcaraan dinamik, kita boleh melihat pendekatan bawah ke atas yang popular di mana kita membina tatasusunan dp untuk menjejaki sama ada adalah mungkin untuk memecahkan s kepada perkataan dalam wordDict pada setiap indeks.

Setiap indeks $i$i dalam tatasusunan dp akan menunjukkan sama ada mungkin untuk memecahkan keseluruhan rentetan menjadi perkataan bermula pada indeks $i$i .

Note

dp needs to be of size s.length 1 to hold the edge case of an empty string, in other words, when we're out of bounds.

Mari kita ciptanya dengan nilai palsu pada mulanya:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true

Explanation: Return true because "leetcode" can be segmented as "leet code".

Indeks terakhir ialah rentetan kosong, yang boleh dianggap boleh pecah, atau dengan kata lain, sah:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Melangkah ke belakang, untuk setiap indeks s, kita boleh menyemak sama ada sebarang perkataan dalam wordDict boleh dicapai dari indeks itu dan seterusnya:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Jika kita masih dalam batas s (i word.length <= s.length) dan kita menjumpai perkataan (s.slice(i, i word.length) === word), kita akan tandakan slot itu sebagai nilai kebenaran "kedudukan seterusnya" yang boleh kita putuskan rentetan, iaitu i word.length:

let dp = Array.from({ length: s.length + 1 }, () => false); // +1 for the base case, out of bounds




<p>Jika kita boleh memecahkannya menjadi <em>mana-mana</em> perkataan dalam wordDict, kita tidak perlu terus melihat perkataan lain, jadi kita boleh keluar dari gelung:<br>
</p>

<pre class="brush:php;toolbar:false">dp[s.length] = true; // base case

Akhir sekali, kami mengembalikan dp[0] — jika keseluruhan rentetan boleh dipecahkan kepada perkataan dalam wordDict, nilainya akan disimpan benar, sebaliknya palsu:

for (let i = s.length - 1; i >= 0; i--) {
  for (const word of wordDict) {
    /* ... */
  }
}

Dan, inilah penyelesaian muktamad:

for (let i = s.length - 1; i >= 0; i--) {
  for (const word of wordDict) {
    if (i + word.length <= s.length && s.slice(i, i + word.length) === word) {
      dp[i] = dp[i + word.length];
    }
    /* ... */
  }
}

Kerumitan masa dan ruang

Kerumitan masa ialah $O(n\ast m\ast t)$O(n∗m∗t) di mana $n$n ialah rentetan s, $m$m ialah bilangan perkataan dalam wordDict, dan $t$t ialah perkataan panjang maksimum dalam wordDict — kerana kami mempunyai gelung bersarang yang berjalan melalui setiap perkataan dalam wordDict dengan operasi hirisan yang menggunakan word.length untuk setiap aksara dalam s.

Kerumitan ruang adalah $O(n)$O(n) kerana tatasusunan dp yang kami simpan untuk setiap indeks s.

---

Masalah pengaturcaraan dinamik terakhir dalam siri ini ialah Susulan Bertambah Terpanjang. Sehingga itu, selamat mengekod.

Atas ialah kandungan terperinci Meditasi LeetCode: Pecah Kata. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!