LeetCode—Word Break

LeetCode—Word Break

Given a string s and a dictionary of words dict, determine ifs 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".

在這個例子當中，主要是為了看一個句子字符串中的詞語能不能夠都劃分為詞典中的詞語

flag[j]為true，那麼就是要求存在一個變量k,能夠滿足flag[k]為ture,同時substr(k,j-k)是在字典當中的

但是在這個例子當中是不關心最終的劃分方式

    class Solution {  
    public:  
        bool wordBreak(string s, unordered_set &dict) {  
            int length = s.size();
	vector val(length+1,false);
	val[0] = true; //<根據長度進行設置
	int i = 0;
	int j = 0;
	for(i = 0; i < length; i++)
	{
		if(val[i])//<前一個長度是可以進行分解的
		{
			for(j = 1; (i+j) <= length; j++)
			{
				string tmp = s.substr(i,j);
				if(dict.count(tmp) > 0)
				{
					val[i+j] = true;
				}
			}
		}
	}
	return val[length];
        }  
    };  

Word Break II

Given a string s and a dictionary of words dict, add spaces ins 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"].

有一種方法是DFS 方法，還沒有研究

這裡主要還是借鑒了第一個例子當中的方法，先檢測是否能夠被劃分，如果可以被劃分，之後再通過遍歷進行存儲

class Solution {
public:
    void breakWord(vector &res, string &s, unordered_set &dict, string str, int idx, vector &dp) {
        string substr;
        for (int len = 1; idx + len <= s.length(); ++len) {
            if (dp[idx + len] && dict.count(s.substr(idx,len)) > 0) {
                substr = s.substr(idx, len);
                if (idx + len < s.length()) {
                    breakWord(res, s, dict, str + substr + " ", idx + len, dp);
                } else {
                    res.push_back(str + substr);
                    return;
                }
            }
        }
    }
    
    vector wordBreak(string s, unordered_set &dict) {
        vector dp(s.length() + 1, false);
        dp[0] = true;
        for (int i = 0; i < s.length(); ++i) {
            if (dp[i]) {
                for (int len = 1; i + len <= s.length(); ++len) {
                    if (dict.count(s.substr(i, len)) > 0) {
                        dp[i + len] = true;
                    }
                }
            }
        }
        vector res;
        if (dp[s.length()]) 
            breakWord(res, s, dict, "", 0, dp);
        return res;
    }
};