139. Word Break 以及 140.Word Break II

139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given

s = 

"leetcode"

,

dict = 

["leet", "code"]

.

Return true because 

"leetcode"

 can be segmented as 

"leet code"

.

思路：

定義狀态矩陣dp[i]表示0-i能被切割,需要先找到0-（j -1），然後j -i 這個區間是否是字典裡面的，這樣找。思路就是序列性動态規劃，事件複雜度是n^2.

注意本題的初始化方法，需要從0開始進行查找符合條件的字典字元串，要找到從0位置開始的所有符合條件的字元串，比如go,goal,goals。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if(s.size() == 0){
            return false;
        }
        if(wordDict.size() == 0){
            return 0;
        }
        int n = s.size();
        vector<bool> dp(n,false);
        //hashset
        unordered_set<string> wordSet;
        for(int i = 0;i < wordDict.size();++i){
            wordSet.insert(wordDict[i]);
        }
        //find first true
        int ix = 0;
        for(ix = 0;ix < n;++ix){            
            if(wordSet.find(s.substr(0,ix + 1)) != wordSet.end()){
                dp[ix] = true;
                //break;             
            }
        }
        // if(ix == n){
        //     return dp[ix - 1];
        // }開始這裡沒注釋，直接每次退出循環ix都等于n，總是出錯，因為是原來break掉，才有這句
        //funciton
        for(int i = 0;i < n;++i){
            for(int j = 1;j <= i;++j){                 
                if((dp[j - 1] == true) && (wordSet.find(s.substr(j,i - j + 1)) != wordSet.end())){
                    dp[i] = true;                   
                }
            }
        }
        
        return dp[n - 1];
    }
};      

Word breakII需要找出所有符合條件的分割字元串，并且輸出。首先考慮DFS模闆，這裡的巧妙之處就是start取代了j這個變量，但是複雜度還是平方級别。不熟悉的是string的append，insert，erase（pos,arg），記住是包含pos位置的。參考：水中的魚

class Solution {
public:
    void helper(unordered_set<string> &wordSet,vector<string> &res,string &s,string &tmp,int start){
        if(start == s.size()){           
            res.push_back(tmp.substr(0,tmp.size() - 1));
        }
        for(int i = start;i < s.size();++i){
            string sub = s.substr(start,i - start + 1);
            if( wordSet.find(sub) == wordSet.end()){
                continue;
            }            
            tmp.append(sub).append(" ");//隻有每步滿足條件之後才開始位置為該步的下一步            
            helper(wordSet,res,s,tmp,i + 1);            
            tmp.erase(tmp.size() - sub.size() - 1);
        }
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        
        if(s.size() == 0){
            return {};
        } 
        if(wordDict.size() == 0){
             return {};
        }        
        vector<string> res;
        unordered_set<string> wordSet;
        for(string tmp : wordDict){
            wordSet.insert(tmp);
        }
        string tmp;       
        helper(wordSet,res,s,tmp,0);
        return res;       
    }
};      

這樣有很多重複計算，需要引入一個isOK矩陣，記錄之前通路的結果，如果在之前i這個位置已經切割了一次，并且沒有找到結果，那麼就是false，下次不需要再通路了。這裡首先都初始化為true。

int oldSize = res.size();
helper(wordSet,res,s,tmp,i + 1,isOk);
if(oldSize == res.size()){
    isOk[i] = false;
}      

這裡了解起來比較困難，記住每次經過helper函數應該是有一個結果壓入res中的，但是前後size一樣大，是以從i這個元素切割沒有的得到結果，那下次切割到這個i的時候，就不需要再計算了，直接跳過。

class Solution {
public:
    void helper(unordered_set<string> &wordSet,vector<string> &res,string &s,string &tmp,int start,vector<bool> &isOk){
        if(start == s.size()){           
            res.push_back(tmp.substr(0,tmp.size() - 1));
        }
        for(int i = start;i < s.size();++i){
            string sub = s.substr(start,i - start + 1);
            if((isOk[i] == false) || wordSet.find(sub) == wordSet.end()){
                continue;
            }
            
            tmp.append(sub).append(" ");//隻有每步滿足條件之後才開始位置為該步的下一步
            int oldSize = res.size();
            helper(wordSet,res,s,tmp,i + 1,isOk);
            if(oldSize == res.size()){
                isOk[i] = false;
            }
            tmp.erase(tmp.size() - sub.size() - 1);
        }
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        
        if(s.size() == 0){
            return {};
        } 
        if(wordDict.size() == 0){
             return {};
        }        
        vector<string> res;
        unordered_set<string> wordSet;
        for(string tmp : wordDict){
            wordSet.insert(tmp);
        }
        string tmp;
        vector<bool> isOk(s.size(),true);//代表從i位置分割是否能得到一個結果
        //isOk[0] = false;
        helper(wordSet,res,s,tmp,0,isOk);
        return res;       
    }
};      

轉載于:https://www.cnblogs.com/dingxiaoqiang/p/7719748.html