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
• 1
• 1
• 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

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

Jika kita boleh memecahkannya menjadi mana-mana perkataan dalam wordDict, kita tidak perlu terus melihat perkataan lain, jadi kita boleh keluar dari gelung:

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 



<h4>
  
  
  Kerumitan masa dan ruang
</h4>

<p>Kerumitan masa ialah 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>∗</mo><mi>m</mi><mo>∗</mo><mi>t</mi><mo stretchy="false">)</mo></mrow>O(n * m * t) </semantics></math><span><span>O(n∗</span><span>m∗</span><span>t)</span></span></span>
</span>
 di mana 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow>n </semantics></math><span><span>n</span></span></span>
</span>
 ialah rentetan s, 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow>m </semantics></math><span><span>m</span></span></span>
</span>
 ialah bilangan perkataan dalam wordDict, dan 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi></mrow>t </semantics></math><span><span>t</span></span></span>
</span>
 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.</p>

<p>Kerumitan ruang adalah 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow>O(n) </semantics></math><span><span>O(n)</span></span></span>
</span>
 kerana tatasusunan dp yang kami simpan untuk setiap indeks s.</p>


<hr>

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


          

            
  

            
        

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