zangdaiyang 2020-06-25
题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/word-break
给定一个非空字符串 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
思路:动态规划
动态规划的方法,主要是将问题细化。这里以示例 2 来大致解释下:
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true
在这里,如果要判断 applepenapple
是否能够被拆分,可将问题转化为前面 j 个字符是否能够被拆分在加上剩下的子串是否为单词表中的单词,例如:
applepen
能否被拆分,加上 apple
如果可以,那么就表示整体能够拆分。
设 dp[i]
为前 i 个子串能够拆分,那么具体的算法如下:
dp[i]
是否为真,如上所述,判断划分的两部分前面部分是否为真,后面部分是否在单词表中:dp[j]
是否为真具体的实现代码如下。
class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: # 初始化 dp dp = [False] * (len(s) + 1) dp[0] = True # 遍历字符串 for i in range(1, len(s)+1): # j 逐渐划分字符串 for j in range(i, -1, -1): # 判断前缀部分是否为真以及后面剩余部分是否在单词表中 dp[i] = dp[j] and (s[j:i] in wordDict) # 如果为真跳出循环,这里已经判定可以拆分,没必要继续 if dp[i]: break return dp[len(s)]
dp[i]
为前 i 个子串能够被拆分,判断 dp[i]
是否为真则取决于以下部分:文章原创,如果觉得写得还可以,欢迎关注点赞。公众号《书所集录》同步更新,同样欢迎关注点赞。