给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明: 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。,编写代码
时间: 2024-09-25 18:05:26 浏览: 64
给定这样的问题,你可以使用动态规划的方法来解决。首先,我们需要创建一个布尔数组 dp,其中 dp[i] 表示字符串 s 的前 i 个字符是否可以用字典中的单词拼接得到。以下是 Python 代码的一个例子:
```python
def wordBreak(s, wordDict):
word_dict_set = set(wordDict)
n = len(s)
dp = [False] * (n + 1)
# 初始化边界条件,单个字符可以直接匹配
for word in word_dict_set:
if s[0] == word[0]:
dp[0] = word == s[:len(word)]
# 动态规划过程
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_dict_set:
dp[i] = True
break
return dp[-1]
```
这个函数首先将字典转换成集合以加快查找速度,然后初始化 dp 数组,如果第一个字符能组成一个字典中的词,则 dp[0] 设置为真。接着遍历字符串,对于每个位置 i,检查从 0 到 i-1 的所有子串能否构成字典中的词,并且与当前字符相连接,如果能则更新 dp[i] 为真。最后,返回 dp[n] 即表示整个字符串是否可以用字典中的单词拆分。
阅读全文