LeetCode[139] Word Break

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

摘要：復(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; 
}

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

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65265.html

相關(guān)文章

leetcode-139-Word Break

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

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

摘要：所以只要驗證滿足這個條件，我們則可以確定這個較長的字符串也是可分解的。同時，我們用數(shù)組記錄下字符串長度遞增時可分解的情況，以供之后使用，避免重復(fù)計算。當(dāng)遍歷完這個詞典并找出所有以第一個字母開頭的詞以后，我們進(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 評論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 評論0 收藏0
leetcode140. Word Break II

摘要：題目要求現(xiàn)在有一個非空字符串和一個非空的字典?，F(xiàn)在向中添加空格從而構(gòu)成一個句子，其中這個句子的所有單詞都存在與中。題目要求 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 評論0 收藏0
leetcode-140- Word Break II

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

joyvw 2019-07-30 17:28 評論0 收藏0