亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

leetcode140. Word Break II

huayeluoliuhen / 761人閱讀

摘要：題目要求現(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 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"].

現(xiàn)在有一個(gè)非空字符串s和一個(gè)非空的字典wordDict?，F(xiàn)在向s中添加空格從而構(gòu)成一個(gè)句子，其中這個(gè)句子的所有單詞都存在與wordDic中。字典中不包含重復(fù)的單詞。

思路和代碼

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

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

但是單純的遞歸會(huì)帶來(lái)超時(shí)的情況，尤其是當(dāng)字典中的單詞出現(xiàn)大量包含的情況，如:[a,aa,aaa,aaaa]，而輸入為aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
我們可以利用HashMap緩存來(lái)解決這個(gè)問題，其中key為子字符串，value為其分割的結(jié)果的列表。

    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;
    }


想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/68643.html

相關(guān)文章

  • leetcode-140- Word Break II

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

    joyvw 評(píng)論0 收藏0

  • Word Break I, II & Concatenated Words

    摘要：所以現(xiàn)在里面應(yīng)該存可以使長(zhǎng)度為所有可能的里的最后一個(gè)。有兩種寫法，一個(gè)就是直接寫成數(shù)組的形式，不能形成的。結(jié)束之后，第二步就是通過(guò)里面保存的，一步一步回溯找到所有結(jié)果。直接的會(huì)超時(shí)，考慮記憶化搜索。所以事先對(duì)排序。 Word Break 鏈接：https://leetcode.com/problems... 這種找一個(gè)詞由多個(gè)詞組成的題，是拿dp或者dfs來(lái)解，dp本質(zhì)上其實(shí)也是dfs...

    sunsmell 評(píng)論0 收藏0

  • leetcode126. Word Ladder II

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

    cooxer 評(píng)論0 收藏0

  • [LeetCode] 126. Word Ladder II

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

    wayneli 評(píng)論0 收藏0

  • [Leetcode] Word Break 單詞分解

    摘要：所以只要驗(yàn)證滿足這個(gè)條件，我們則可以確定這個(gè)較長(zhǎng)的字符串也是可分解的。同時(shí)，我們用數(shù)組記錄下字符串長(zhǎng)度遞增時(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 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<