成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

[Leetcode] Word Break 單詞分解

Ververica / 1352人閱讀

摘要：所以只要驗(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 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".
動(dòng)態(tài)規(guī)劃 復(fù)雜度

時(shí)間 O(N^2) 空間 O(N)

思路

如果一個(gè)單詞存在一種分解方法，分解后每一塊都在字典中，那必定滿足這么一個(gè)條件：對(duì)于該單詞的最后一個(gè)分割點(diǎn)，這個(gè)分割點(diǎn)到單詞末尾所組成的字符串是一個(gè)單詞，而這個(gè)分割點(diǎn)到單詞開頭所組成的字符串也是可分解的。所以只要驗(yàn)證滿足這個(gè)條件，我們則可以確定這個(gè)較長的字符串也是可分解的。

finishleetcode
finishleetco de
true         false
finishleet code
false      true
finish leetcode
true   true

所以我們用外層循環(huán)來控制待驗(yàn)證的字符串的長度，而用內(nèi)層的循環(huán)來尋找這么一個(gè)分割點(diǎn)，可以把字符串分成一個(gè)單詞和一個(gè)同樣可分解的子字符串。同時(shí)，我們用數(shù)組記錄下字符串長度遞增時(shí)可分解的情況，以供之后使用，避免重復(fù)計(jì)算。

代碼 
public class Solution {
    public boolean wordBreak(String s, Set wordDict) {
        boolean[] dp = new boolean[s.length()+1];
        Arrays.fill(dp,false);
        dp[s.length()]=true;
        // 外層循環(huán)遞增長度
        for(int i = s.length()-1; i >=0 ; i--){
            // 內(nèi)層循環(huán)尋找分割點(diǎn)
            for(int j = i; j < s.length(); j++){
                String sub = s.substring(i,j+1);
                if(wordDict.contains(sub) && dp[j+1]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }
}
Word Break II 
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.


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"].
動(dòng)態(tài)規(guī)劃 復(fù)雜度

時(shí)間 O(N^2) 空間 O(N^2)

思路

我們從第一個(gè)字母開始，遍歷字典，看從第一個(gè)字母開始能組成哪個(gè)在字典里的詞，如果找到一個(gè)，就在這個(gè)詞的結(jié)束位置下一個(gè)字母處，建立一個(gè)列表，記錄下這個(gè)詞（保存到一個(gè)列表的數(shù)組）。當(dāng)遍歷完這個(gè)詞典并找出所有以第一個(gè)字母開頭的詞以后，我們進(jìn)入下一輪搜索。下一輪搜索只在之前找到的詞的后面位置開始，如果這個(gè)位置不是一個(gè)詞的下一個(gè)字母位置，我們就跳過。這樣我們相當(dāng)于構(gòu)建了一個(gè)樹（實(shí)際上是列表數(shù)組），每個(gè)找到的詞都是這個(gè)樹的一個(gè)分支。有了這個(gè)“樹”，然后我們?cè)儆蒙疃葍?yōu)先搜索，把路徑加到結(jié)果當(dāng)中就行了。

c
a
t                *              *
s -- cat         |              |
a -- cats        cats          cats
n                             /
d                            /
d -- and, sand      and    sand
o                          /
g                         /
  -- dog                dog
注意

在backtracking的時(shí)候不用考慮下標(biāo)超界（小于0）的情況，直接將所有到0的都加入結(jié)果就行了，因?yàn)槲覀冊(cè)诮ㄟ@個(gè)路徑時(shí)，就是從0開始建的，不可能超界。

代碼 
public class Solution {
    
    public List res = new LinkedList();
    
    public List wordBreak(String s, Set wordDict) {
        List dp[] = new ArrayList[s.length()+1];
        dp[0] = new ArrayList();
        for(int i = 0; i < s.length(); i++){
            // 只在單詞的后一個(gè)字母開始尋找，否則跳過
            if(dp[i]==null) continue;
            // 看從當(dāng)前字母開始能組成哪個(gè)在字典里的詞
            for(String word : wordDict){
                int len = word.length();
                if(i + len > s.length()) continue;
                String sub = s.substring(i, i+len);
                if(word.equals(sub)){
                    if(dp[i + len] == null){
                        dp[i + len] = new ArrayList();
                    }
                    dp[i + len].add(word);
                }
            }
        }
        // 如果數(shù)組末尾不存在單詞，說明找不到分解方法
        if(dp[s.length()]!=null) backTrack(dp, s.length(), new ArrayList());
        return res;
    }
    
    private void backTrack(List dp[], int end, ArrayList tmp){
        if(end <= 0){
            String path = tmp.get(tmp.size()-1);
            for(int i = tmp.size() - 2; i >= 0; i--){
                path += " " + tmp.get(i);
            }
            res.add(path);
            return;
        }
        for(String word : dp[end]){
            tmp.add(word);
            backTrack(dp, end - word.length(), tmp);
            tmp.remove(tmp.size()-1);
        }
    }
}

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

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

相關(guān)文章

  • 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 評(píng)論0 收藏0

  • [Leetcode] Length of Last Word 最后一個(gè)單詞長度

    摘要：代碼雙指針法復(fù)雜度時(shí)間空間思路從后往前看字符串，跳過所有空格后，記下該結(jié)束位置，再到下一個(gè)空格，再記錄一個(gè)開始位置，則長度就是結(jié)束位置減去開始位置。 Length of Last Word Given a string s consists of upper/lower-case alphabets and empty space characters , return the l...

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

  • [Leetcode] Alien Dictionary 外文字典

    摘要：拓?fù)渑判驈?fù)雜度時(shí)間空間思路首先簡單介紹一下拓?fù)渑判?，這是一個(gè)能夠找出有向無環(huán)圖順序的一個(gè)方法假設(shè)我們有條邊，先將每個(gè)節(jié)點(diǎn)的計(jì)數(shù)器初始化為。最后，我們開始拓?fù)渑判?，從?jì)數(shù)器為的字母開始廣度優(yōu)先搜索。 Alien Dictionary There is a new alien language which uses the latin alphabet. However, the ord...

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

  • Word Squares

    摘要：題目鏈接暴力遍歷，一個(gè)一個(gè)檢查看符不符合要求。首先這種需要求出所有結(jié)果的題，一般都是用的。因?yàn)轭}目已經(jīng)說了的長度范圍是到，最多考慮五個(gè)單詞即可。首先是肯定都需要的，兩種或者。如果題目要求返回所有以特定的開頭的單詞，那么可以用。 Valid Word Square 題目鏈接：https://leetcode.com/problems... 暴力遍歷，一個(gè)一個(gè)檢查看符不符合要求。 ...

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

  • 890-查找和替換模式

    摘要：前言的的題目查找和替換模式，原題目描述如下你有一個(gè)單詞列表和一個(gè)模式，你想知道中的哪些單詞與模式匹配。如果存在字母的排列，使得將模式中的每個(gè)字母替換為之后，我們就得到了所需的單詞，那么單詞與模式是匹配的。 前言 LeetCode的Weekly Contest 98的題目查找和替換模式，原題目描述如下： 你有一個(gè)單詞列表 words 和一個(gè)模式 pattern，你想知道 words 中...

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

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

0條評(píng)論

閱讀需要支付1元查看
<