LeetCode[139] Word Break

wyk1184 發(fā)布于2019-08-14 15:04 / 2996人閱讀

摘要：復(fù)雜度思路用來記錄已經(jīng)判斷過的，每次判斷是否開頭是在中的出現(xiàn)的字符串。代碼保留已經(jīng)搜索過的信息

LeetCode[139] Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

DFS + Memorization

復(fù)雜度
O(N^2),O(N)

思路
用map來記錄已經(jīng)判斷過的string，每次判斷是否開頭是在map中的出現(xiàn)的字符串。

代碼

Map map = new HashMap<>();
public boolean wordBreak(String s, Set wordDict) {
    if(s.length() == "") return true;
    // use map to 保留已經(jīng)搜索過的信息；
    if(map.containsKey(s)) return map.get(s);
    for(String d : wordDict) {
        if(s.startsWith(d)) {
            if(wordBreak(s.substring(d.length()), wordDict) {
                return true;
            }
        }
    }
    map.put(s, false);
    return false; 
}

云服務(wù)器 GPU云服務(wù)器 break-word word-break 139企業(yè)郵箱 LeetCode

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/65265.html

相關(guān)文章

leetcode-139-Word Break

摘要：邊界點(diǎn)注意區(qū)分清楚，連貫起來。應(yīng)用思想應(yīng)用，涉及到前后需要保持狀態(tài)的匹配計(jì)算，要保留并利用中間狀態(tài)。相似問題動(dòng)態(tài)規(guī)劃，利用前面的狀態(tài)。題目簡介： 1.完全按照dict中的word進(jìn)行切分匹配，一個(gè)char都不差 2.由于是連續(xù)匹配，所以是首尾相接，所以涉及到動(dòng)態(tài)規(guī)劃思想,需要保留上一個(gè)動(dòng)態(tài) 3.廣度遞歸非常耗時(shí)，不知道什么原因。 4.邊界點(diǎn)注意區(qū)分清楚，連貫起來。應(yīng)用：思想應(yīng)用，涉...

wwolf 2019-07-30 17:28 評(píng)論0 收藏0
[Leetcode] Word Break 單詞分解

摘要：所以只要驗(yàn)證滿足這個(gè)條件，我們則可以確定這個(gè)較長的字符串也是可分解的。同時(shí)，我們用數(shù)組記錄下字符串長度遞增時(shí)可分解的情況，以供之后使用，避免重復(fù)計(jì)算。當(dāng)遍歷完這個(gè)詞典并找出所有以第一個(gè)字母開頭的詞以后，我們進(jìn)入下一輪搜索。 Word Break I Given a string s and a dictionary of words dict, determine if s can ...

Ververica 2019-08-14 12:24 評(píng)論0 收藏0
[LintCode/LeetCode] Word Break

Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...

dunizb 2019-08-14 15:30 評(píng)論0 收藏0
leetcode140. Word Break II

摘要：題目要求現(xiàn)在有一個(gè)非空字符串和一個(gè)非空的字典。現(xiàn)在向中添加空格從而構(gòu)成一個(gè)句子，其中這個(gè)句子的所有單詞都存在與中。題目要求 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence ...

huayeluoliuhen 2019-08-15 14:29 評(píng)論0 收藏0
leetcode-140- Word Break II

摘要：銜接點(diǎn)在于的前后連貫，拼成所有的滿足條件的前后兩個(gè)要連續(xù)。遞歸問題，要記得設(shè)置終止退出條件設(shè)置成形式，就不需要過程中了，直接在此進(jìn)行疊加累計(jì)應(yīng)用將一個(gè)連續(xù)序列分成所有元素可能的組合情況。重點(diǎn)明確不必要的地方，可以不用去進(jìn)行計(jì)算。題目闡述：廣度搜索問題。計(jì)算出所有可能的情況。銜接點(diǎn)在于segs的前后連貫，拼成所有的滿足條件的segs 前后兩個(gè)seg要連續(xù)。遞歸問題，要記得設(shè)置終...

joyvw 2019-07-30 17:28 評(píng)論0 收藏0