[LeetCode] word break 문자열의 구분

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" .
사고방식: 동태적 기획.bool 그룹 마크를 신청합니다.false로 초기화합니다. 
marks[i] =true if 1)s.substr(0,i)는 사전의 단어입니다.
2) 또는 j가 존재하여marks[j]=true 그리고 s.substr(j+1,i)는 사전의 단어입니다.
코드:

    bool wordBreak(string s, unordered_set<string> &dict)
    {
            bool* marks = new bool[ s.length() ];
            memset(marks, 0, s.length() ); //   
    
            for(int i=0; i<s.length(); i++)
            {   
                    if( dict.find( s.substr(0, i+1) ) != dict.end() )
                            *(marks+i) = true;
                            
                    if(i>0)
                            for(int j=0; j<i; j++)
                            {   
                                    if( *(marks+j)==true && ( dict.find( s.substr(j+1, i-j) ) != dict.end() ) )
                                    {   
                                            *(marks+i) = true;
                                            break;
                                    }   
                            }   
            }   
            return *(marks+s.length()-1);
    }

----------------------------------------------------------------------
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"] .
다음 코드는wordbreak의 결과를 출력할 수 있습니다.

    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        
        vector< vector<string> > wordBreaks; //wordBreaks[i]  s.substr(0,i)      break   
        
        int len = s.length();
        
        for(int i=0; i<len; i++)
        {
            vector<string> vec;
            wordBreaks.push_back(vec);

            if(dict.find( s.substr( 0, i+1) ) != dict.end())
            {
                string str = s.substr( 0, i+1 );
                wordBreaks[i].push_back(str);
            }
             
            if(i>0)
                for(int j=0; j<i; j++)
                {
                    
                    if( wordBreaks[j].size() > 0 && dict.find( s.substr( j+1, i-j ) ) != dict.end() )
                    {
                        for(int k=0; k<wordBreaks[j].size(); k++)
                        {
                            string str = wordBreaks[j][k];
                            str = str + " " + s.substr( j+1, i-j );
                            wordBreaks[i].push_back(str);   
                        }
                    }
                }
            
        }
        
        
        return wordBreaks[len-1];
    }