分类
- 题目
- 解题思路
- Python实现
题目
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词，地址。
说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例1
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
解题思路
题目的标签是动态规划，是动态规划下的“背包问题”。从后往前，每次先确定当前要查找的子序列(0:i)，再检查子序列中[j:i]是否在wordDict中并且要保证分割处以前的序列也是在词典中，所以需要一个数组dp来记录当前子序列j是否在词典里。
Python实现
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
]
)
