分類
- 題目
- 解題思路
- Python實現(xiàn)
題目
給定一個非空字符串 s 和一個包含非空單詞列表的字典 wordDict，判定 s 是否可以被空格拆分為一個或多個在字典中出現(xiàn)的單詞，地址。
說明：
- 拆分時可以重復(fù)使用字典中的單詞。
- 你可以假設(shè)字典中沒有重復(fù)的單詞。
示例1
輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因為 "leetcode" 可以被拆分成 "leet code"。
示例2
輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false
解題思路
題目的標簽是動態(tài)規(guī)劃，是動態(tài)規(guī)劃下的“背包問題”。從后往前，每次先確定當前要查找的子序列(0:i)，再檢查子序列中[j:i]是否在wordDict中并且要保證分割處以前的序列也是在詞典中，所以需要一個數(shù)組dp來記錄當前子序列j是否在詞典里。
Python實現(xiàn)
class
Solution
:
def
wordBreak
(
self
,
s
:
str
,
wordDict
:
List
[
str
]
)
-
>
bool
:
length
=
len
(
s
)
dp
=
[
False
for
_
in
range
(
length
+
1
)
]
dp
[
0
]
=
True
for
i
in
range
(
length
+
1
)
:
for
j
in
range
(
i
-
1
,
-
1
,
-
1
)
:
if
dp
[
j
]
and
s
[
j
:
i
]
in
wordDict
:
dp
[
i
]
=
True
break
return
(
dp
[
length
]
)
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
