做公益網(wǎng)站需要什么資質(zhì)免費(fèi)網(wǎng)頁(yè)模板網(wǎng)站
- 難度: 中等
- 通過(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]