[Leetcode] Word Break 單詞分解

Ververica 發布于2019-08-14 12:24 / 1288人閱讀

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

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".

動態規劃 復雜度

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

思路

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

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

所以我們用外層循環來控制待驗證的字符串的長度，而用內層的循環來尋找這么一個分割點，可以把字符串分成一個單詞和一個同樣可分解的子字符串。同時，我們用數組記錄下字符串長度遞增時可分解的情況，以供之后使用，避免重復計算。

代碼

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;
        // 外層循環遞增長度
        for(int i = s.length()-1; i >=0 ; i--){
            // 內層循環尋找分割點
            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"].

動態規劃 復雜度

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

思路

我們從第一個字母開始，遍歷字典，看從第一個字母開始能組成哪個在字典里的詞，如果找到一個，就在這個詞的結束位置下一個字母處，建立一個列表，記錄下這個詞（保存到一個列表的數組）。當遍歷完這個詞典并找出所有以第一個字母開頭的詞以后，我們進入下一輪搜索。下一輪搜索只在之前找到的詞的后面位置開始，如果這個位置不是一個詞的下一個字母位置，我們就跳過。這樣我們相當于構建了一個樹（實際上是列表數組），每個找到的詞都是這個樹的一個分支。有了這個“樹”，然后我們再用深度優先搜索，把路徑加到結果當中就行了。

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

注意

在backtracking的時候不用考慮下標超界（小于0）的情況，直接將所有到0的都加入結果就行了，因為我們在建這個路徑時，就是從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++){
            // 只在單詞的后一個字母開始尋找，否則跳過
            if(dp[i]==null) continue;
            // 看從當前字母開始能組成哪個在字典里的詞
            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);
                }
            }
        }
        // 如果數組末尾不存在單詞，說明找不到分解方法
        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);
        }
    }
}

云服務器 GPU云服務器 break-word word-break LeetCode LeetCode_String

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

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

leetcode140. Word Break II

摘要：題目要求現在有一個非空字符串和一個非空的字典。現在向中添加空格從而構成一個句子，其中這個句子的所有單詞都存在與中。題目要求 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] Length of Last Word 最后一個單詞長度

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

happen 2019-08-14 12:46 評論0 收藏0
[Leetcode] Alien Dictionary 外文字典

摘要：拓撲排序復雜度時間空間思路首先簡單介紹一下拓撲排序，這是一個能夠找出有向無環圖順序的一個方法假設我們有條邊，先將每個節點的計數器初始化為。最后，我們開始拓撲排序，從計數器為的字母開始廣度優先搜索。 Alien Dictionary There is a new alien language which uses the latin alphabet. However, the ord...

pkhope 2019-08-14 12:38 評論0 收藏0
Word Squares

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

JerryZou 2019-08-14 17:19 評論0 收藏0
890-查找和替換模式

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

haobowd 2019-08-19 10:59 評論0 收藏0