跟着leedcode刷算法–字符串2

这是我参与11月更文挑战的第6天，活动详情查看：2021最后一次更文挑战

题三：

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。

示例 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 中的所有字符串 互不相同

相关标签

• 字典树
• 记忆化搜索
• 哈希表
• 字符串
• 动态规划

动态规划思路：

• 对s进行拆分，s[0..j-1]和s[j:i]两个部分，其中j = 0..i-1
• 判断以上两个部分是否在wordDict中，而s[0..j-1]可以用dp[j]替代

代码：

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [True]+[False for _ in range(len(s))]
        for i in range(1,len(s)+1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break 
        return dp[len(s)]
复制代码

运行结果：

第四题：

单词拆分 II

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：

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

示例 2：

输入:

s = "pineapplepenapple"

wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]

输出:

[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]

解释: 注意你可以重复使用字典中的单词。

示例 3：

输入:

s = "catsandog"

wordDict = ["cats", "dog", "sand", "and", "cat"]

输出:
[]

相关标签

• 字典树
• 记忆化搜索
• 哈希表
• 字符串
• 动态规划
• 回溯

这个题和之前的分割回文串思路很像都是dfs算法

话不多说，直接上代码

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:        
        def dfs(n):
            if n == len(s):
                res.append(" ".join(list(items)))
                return
            
            for i in range(n,len(s)):
                if s[n:i + 1] in wordDict:
                    items.append(s[n:i + 1])  
                    dfs(i + 1)
                    items.pop()
        
        res = []
        items = []
        dfs(0)
        return res
复制代码

执行结果：

对比一下分割回文算法：

很多题都很相似，大家可以灵活运用一下