Leetcode--Word Break

Problem Description:

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

分析：

這個題目最容易想到的是利用遞歸，不斷地拆分出在字典中的單詞，然後遞歸判斷後綴是否能被拆分，後來想著利用利用字典中的單詞最大最小長度提高效率，結果還是超時，具體代碼如下：

class Solution {
public:
    int minlen,maxlen;
    void findlen(unordered_set &dict)
    {
        unordered_set::iterator iter=dict.begin();
        minlen=(*iter).length();
        maxlen=(*iter).length();
        for(iter=dict.begin();iter!=dict.end();++iter)
        {
            if((*iter).length()maxlen)
                maxlen=(*iter).length();
        }
    }
    
    bool wordcontain(string s, unordered_set &dict,int begin)
    {
        if(begin==s.length())
            return true;
        
        for(int i=minlen;i<=maxlen;++i)
        {
            if((begin+i)>s.length())
                continue;
            if(dict.find(s.substr(begin,i))!=dict.end())
                if(wordcontain(s,dict,begin+i))
                    return true;
        }
        return false;
    }
    
    
    bool wordBreak(string s, unordered_set &dict) {
        if(s.empty()||dict.empty())
            return false;
        findlen(dict);
        return wordcontain(s,dict,0);
        
    }
};

Submission Result: Time Limit Exceeded

Last executed input: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
然後在discuss區看了一些討論，發現應該用動態規劃來實現，利用一個一維bool數組記錄子串是否可被拆分，減少了重復判斷子串的次數，效率明顯提高。 代碼如下：

class Solution {
public:

    bool wordBreak(string s, unordered_set &dict) {
        if(s.empty()||dict.empty())
            return false;
        int len=s.size();
        vector flag(len+1,false);
        flag[0]=true;
        for(int i=1;i<=len;++i)
            for(int j=0;j