【算法题】139. 单词拆分-力扣(LeetCode)

1.题目

下方是力扣官方题目的地址

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意:不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同

2.题解

思路一（深度优先搜索）

这题也可以看作是选择加组合，在wordDict 中选择若干个单词进行拼接，看看能不能拼成s 的样子，可以就是True,否则就是False。

这种情形我们可以联系到树这一数据结构，从而联想到深度优先搜索。

我们以s = "leetcode", wordDict = ["leet", "code"]为例，来画一棵树，然后根据这个树，就很好写出dfs的代码了

在这里插入图片描述

Python代码

class Solution(object):def wordBreak(self, s, wordDict):""":type s: str:type wordDict: List[str]:rtype: bool"""global ansn=len(s)ans=False               # 默认为假def dfs(d,rev):         # rev代表当前拼接好的字符串global ansif len(rev)>=n:    # 判停条件if rev==s:ans=True      # 搜索到了，改为真return                  for i in wordDict:dfs(d+1,rev+i)     # 记录拼接字符，进入下一层 dfs(0,'')return ans

这个方法比较好想到，不过显然超时了

在这里插入图片描述

思路二（动态规划）

当然我们可以使用空间来存储已经解决好的子问题，通过一个个子问题来解决这个问题。

我们可以建立一个数组dp，dp[j]来表示在j之前的字符是否可以被字典里的单词拼接而成，可以就是True，否则就是False。

我们再次以s = "leetcode", wordDict = ["leet", "code"]为例

比如说：dp[4]=True表示s[:4]也就是leet可以被字典里的单词拼接而成

由于前面的字符（s[:4]）可以被拼接而成，所以我们只需要看后面的是否能够被拼接就行了，以此递推下去就行了

我们看看下面的图就会清晰很多了：

在这里插入图片描述

Python代码

class Solution(object):def wordBreak(self, s, wordDict):""":type s: str:type wordDict: List[str]:rtype: bool"""n=len(s)dp=[False]*(n+1)       # 初始化dp数组dp[0]=True             # 默认dp[0]为True，也就是说，''可以被字典里面的单词拼接而成for i in range(n):     if dp[i]==True:    # 如果s[:i]可以被单词拼接而成for j in range(i+1,n+1):        # 那么前面的就不用再看了if s[i:j] in wordDict:  # 直接判断后面的子串是否可以拼接dp[j]=True          # 可以拼接则整个s[:j]都是True了return dp[-1]