• 難度： 中等
• 通過(guò)率： 33.7%
• 題目鏈接：. - 力扣（LeetCode）

題目描述

給定一個(gè)非空字符串?s?和一個(gè)包含非空單詞列表的字典?wordDict，判定?s?是否可以被空格拆分為一個(gè)或多個(gè)在字典中出現(xiàn)的單詞。

說(shuō)明：

• 拆分時(shí)可以重復(fù)使用字典中的單詞。
• 你可以假設(shè)字典中沒(méi)有重復(fù)的單詞。

示例 1：

輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因?yàn)?"leetcode" 可以被拆分成 "leet code"。

示例 2：

輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因?yàn)?"applepenapple" 可以被拆分成 "apple pen apple"。注意你可以重復(fù)使用字典中的單詞。

示例 3：

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

解法：

解法 1. 廣度優(yōu)先搜索

整個(gè)字符串是由多個(gè)單詞拼接而成的，這些單詞的拼接組合構(gòu)成了一顆巨大的樹(shù)。如果有一條路徑上的單詞可以構(gòu)成該字符串，則說(shuō)明有解。但是暴力搜索這個(gè)樹(shù)，其時(shí)間復(fù)雜度為?O(n^n)。

基于廣度優(yōu)先的搜索方法，可以大幅度減少時(shí)間復(fù)雜度。其思想是，在字典中尋找字符串的前綴，然后移除前綴，繼續(xù)尋找前綴。直到最后字符串為空時(shí)，認(rèn)為字典里的單詞可以構(gòu)成該字符串。

下面的代碼中，從下標(biāo) 0 開(kāi)始，尋找前綴字符串，然后將結(jié)尾下標(biāo)入隊(duì)列，下一次取出該值作為新的起始下標(biāo)。

class Solution:def wordBreak(self, s: str, wordDict) -> bool:queue = [0]words = set(wordDict)while queue:start = queue.pop(0)if start == len(s):return Truefor end in range(start+1, len(s)+1):if s[start:end] in words:queue.append(end)return False

但是上面這種方法依然超時(shí)了，動(dòng)態(tài)規(guī)劃能夠得到更低的時(shí)間復(fù)雜度。

解法 2. 動(dòng)態(tài)規(guī)劃

對(duì)于字符串?s，如果?s[:i]?和?s[i:]?均可以由字典中的單詞組成，那么整個(gè)字符串?s?也就可以由字典中單詞組成。

用?dp[i]?表示?s[:i]?是否可由字典中單詞組成。

class Solution:def wordBreak(self, s: str, wordDict) -> bool:dp = [False] * (len(s) + 1)dp[0] = Truewords = set(wordDict)for i in range(1, len(s)+1):for j in range(0, i):if dp[j] and s[j:i] in words:dp[i] = Truebreakreturn dp[-1]