中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁(yè) > news >正文

做公益網(wǎng)站需要什么資質(zhì)免費(fèi)網(wǎng)頁(yè)模板網(wǎng)站

做公益網(wǎng)站需要什么資質(zhì),免費(fèi)網(wǎng)頁(yè)模板網(wǎng)站,ebay賣(mài)家網(wǎng)站建設(shè),網(wǎng)絡(luò)游戲賬號(hào)id及裝備等難度: 中等通過(guò)率: 33.7%題目鏈接:. - 力扣(LeetCode) 題目描述 給定一個(gè)非空字符串 s 和一個(gè)包含非空單詞列表的字典 wordDict,判定 s 是否可以被空格拆分為一個(gè)或多個(gè)在字典中出現(xiàn)的單詞。 說(shuō)明&#…
  • 難度: 中等
  • 通過(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]
http://www.risenshineclean.com/news/54132.html

相關(guān)文章:

  • 制作網(wǎng)站誰(shuí)家做的好合肥百度seo代理
  • 湖南衡陽(yáng)網(wǎng)站建設(shè)怎么樣優(yōu)化網(wǎng)站seo
  • 天津地鐵建設(shè)網(wǎng)站網(wǎng)站鏈接提交
  • 網(wǎng)架加工入門(mén)基礎(chǔ)知識(shí)網(wǎng)站關(guān)鍵詞排名seo
  • 江門(mén)網(wǎng)站建設(shè)開(kāi)發(fā)建立一個(gè)企業(yè)網(wǎng)站需要多少錢(qián)
  • 專(zhuān)門(mén)做諾麗果的網(wǎng)站百度基木魚(yú)建站
  • 榆中建設(shè)局網(wǎng)站站長(zhǎng)工具查詢域名
  • 怎么從網(wǎng)站上看出做網(wǎng)站的日期網(wǎng)頁(yè)快速收錄
  • 企業(yè)網(wǎng)站建設(shè)方案書(shū)范文關(guān)鍵詞挖掘工具有哪些
  • 技術(shù)專(zhuān)業(yè)網(wǎng)站建設(shè)免費(fèi)的關(guān)鍵詞挖掘工具
  • python前端開(kāi)發(fā)北京網(wǎng)站seo哪家公司好
  • 保存的密碼變成亂碼搜索引擎優(yōu)化叫什么
  • 網(wǎng)站互動(dòng)功能網(wǎng)站推廣應(yīng)該怎么做?
  • 上海新聞網(wǎng)頭條新聞seo常用分析的專(zhuān)業(yè)工具
  • 微信如何建商城網(wǎng)站百度投放廣告怎么收費(fèi)
  • 杭州做網(wǎng)站外包公司哪家好優(yōu)化seo網(wǎng)站
  • 江門(mén)網(wǎng)站制作維護(hù)南昌seo公司
  • 政府網(wǎng)站的建設(shè)規(guī)劃設(shè)想seo關(guān)鍵詞排名優(yōu)化哪家好
  • 域名注冊(cè)了 如何做網(wǎng)站如何推廣app賺錢(qián)
  • 機(jī)械網(wǎng)站優(yōu)化百度推廣客戶端怎么登陸
  • 最新開(kāi)的手游傳奇網(wǎng)站seo研究中心晴天
  • 集團(tuán)簡(jiǎn)介ppt優(yōu)秀范例百度網(wǎng)站怎么優(yōu)化排名
  • 怎樣做企業(yè)網(wǎng)站建設(shè)網(wǎng)站推廣與優(yōu)化平臺(tái)
  • 建設(shè)部網(wǎng)站公示公告安全seo推廣的全稱(chēng)是
  • 怎樣開(kāi)通網(wǎng)站網(wǎng)站開(kāi)發(fā)的一般流程
  • 濟(jì)南 網(wǎng)站建設(shè)公司 醫(yī)療湖南關(guān)鍵詞排名推廣
  • 做oa好 還是做網(wǎng)站好網(wǎng)絡(luò)推廣的平臺(tái)有哪些
  • 臨沂市建設(shè)安全管理網(wǎng)站整合營(yíng)銷(xiāo)的最高階段是
  • 網(wǎng)站首頁(yè)菜單欄表怎么做中國(guó)今天最新軍事新聞
  • 數(shù)據(jù)來(lái)源于網(wǎng)站需如何做腳注谷歌推廣怎么樣