leetcode140. Word Break II

huayeluoliuhen 發布于2019-08-15 14:29 / 707人閱讀

摘要：題目要求現在有一個非空字符串和一個非空的字典。現在向中添加空格從而構成一個句子，其中這個句子的所有單詞都存在與中。

題目要求

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 where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

現在有一個非空字符串s和一個非空的字典wordDict。現在向s中添加空格從而構成一個句子，其中這個句子的所有單詞都存在與wordDic中。字典中不包含重復的單詞。

思路和代碼

我們只需要每次從當前字符串中進行一次分割，該分割保證前一部分為字典中的一個單詞，然后我們將后一部分作為子字符串遞歸的傳入方法獲取子字符串的分割。

catsanddog
cat | sanddog
cat | sand | dog 
cats | anddog
cats | and | dog

但是單純的遞歸會帶來超時的情況，尤其是當字典中的單詞出現大量包含的情況，如:[a,aa,aaa,aaaa]，而輸入為aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
我們可以利用HashMap緩存來解決這個問題，其中key為子字符串，value為其分割的結果的列表。

    private Map> cache = new HashMap>();
    public List wordBreak(String s, List wordDict) {
        if(cache.containsKey(s)) return cache.get(s);
        List result = new ArrayList();
        if(s.length()==0){
            result.add("");
            return result;
        }
        
        for(String word : wordDict){
            if(s.startsWith(word)){
                List subWords = wordBreak(s.substring(word.length()), wordDict);
                for(String subWord : subWords){
                    result.add(word + (subWord.isEmpty() ? "" :" ") + subWord);
                }
                
                
            }
        }
        cache.put(s, result);
        return result;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 break-word word-break cdn140 Leetcod

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/68643.html

leetcode-140- Word Break II

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

joyvw 2019-07-30 17:28 評論0 收藏0
Word Break I, II & Concatenated Words

摘要：所以現在里面應該存可以使長度為所有可能的里的最后一個。有兩種寫法，一個就是直接寫成數組的形式，不能形成的。結束之后，第二步就是通過里面保存的，一步一步回溯找到所有結果。直接的會超時，考慮記憶化搜索。所以事先對排序。 Word Break 鏈接：https://leetcode.com/problems... 這種找一個詞由多個詞組成的題，是拿dp或者dfs來解，dp本質上其實也是dfs...

sunsmell 2019-08-14 17:20 評論0 收藏0
leetcode126. Word Ladder II

摘要：題目要求相比于，要求返回所有的最短路徑。至于如何生成該有向圖，則需要通過廣度優先算法，利用隊列來實現。將每一層的分別入棧。如果遇到則至該層結尾廣度優先算法結束。通過這種方式來防止形成圈。題目要求 Given two words (beginWord and endWord), and a dictionarys word list, find all shortest transfo...

cooxer 2019-08-15 11:13 評論0 收藏0
[LeetCode] 126. Word Ladder II

摘要：存放過程中的所有集合為所有的結尾，則順序存放這個結尾對應的中的所有存放同一個循環的新加入的，在下一個循環再依次對其中元素進行進一步的把首個字符串放入新，再將放入，并將鍵值對放入，進行初始化 Problem Given two words (start and end), and a dictionary, find all shortest transformation sequenc...

wayneli 2019-08-14 14:27 評論0 收藏0
[Leetcode] Word Break 單詞分解

摘要：所以只要驗證滿足這個條件，我們則可以確定這個較長的字符串也是可分解的。同時，我們用數組記錄下字符串長度遞增時可分解的情況，以供之后使用，避免重復計算。當遍歷完這個詞典并找出所有以第一個字母開頭的詞以后，我們進入下一輪搜索。 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