LeetCode 冥想：斷詞

此問題的描述是：

給定一個字串 s 和一個字串字典 wordDict，如果 s 可以分割成一個或多個字典單字的空格分隔序列，則傳回 true。

注意字典中的同一個單字在分詞中可能會重複使用多次。

例如：

或：

或：

此外，我們的約束表明wordDict 的所有字串都是**唯一**，並且：

• 1
• 1
• 1
• s 和 wordDict[i] 僅由小寫英文字母組成。

---

繼續動態程式設計解決方案，我們可以看看一種流行的自下而上的方法，我們建立一個 dp 數組來追蹤是否可以在每個索引處將 s 分解為 wordDict 中的單字。

每個索引 $我$我我我$我我我dp\; 陣列中將指示$是否可以將整個字串分解為從索引開始的單字 我

我

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.

我我我我我我我 .

讓我們用最初的錯誤值來建立它：

最後一個索引是空字串，可以認為它是可破壞的，或者換句話說，有效的：

向後看，對於 s 的每個索引，我們可以檢查從該索引開始是否可以到達 wordDict 中的任何單字：

如果我們仍在s 的範圍內(i word.length

如果我們可以將其分解為wordDict中的任何單詞，我們就不必繼續查看其他單詞，因此我們可以跳出循環：

最後，我們傳回 dp[0] - 如果整個字串可以分解為 wordDict 中的單詞，則其值將儲存 true，否則為 false：

而且，這是最終的解決方案：

時間和空間複雜度

時間複雜度為 $O(n*m*t)$O(n*m*t) 在哪裡 $n$nn > 是字串 s， $米$米 是 wordDict 中的單字數，並且 $t$t

t > 是 wordDict 中的最大長度單字 - 因為我們有一個嵌套循環，透過切片操作遍歷 wordDict 中的每個單字，該切片操作使用 s 中每個字元的 word.length。 $O()$n)O(n🎜>

---

O(n) 因為我們為 s 的每個索引儲存 dp 陣列。 該系列中的最後一個動態規劃問題將是最長遞增子序列。在那之前，祝您編碼愉快。

以上是LeetCode 冥想：斷詞的詳細內容。更多資訊請關注PHP中文網其他相關文章！