Word Break II

07/13/2016 Dynamic Programming Backtracking String

Question

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


Solution

Result: Accepted Time: 40 ms

Here should be some explanations.

bool dp[1024][1024]={0};
class Solution {
public:

    void dfs(vector<string> & ret,int cnt,int ptr,const string str,char * buff,
            const int len,const unordered_set<string>& dict)
    {
        for(int i = ptr; i < len; i++)
            {
                buff[cnt++] = str[i];
                buff[cnt] = ' ';
                if(dp[ptr][i] && dict.count(str.substr(ptr,i-ptr+1)))
                {
                    if( i == len -1)
                    {
                        buff[cnt] = 0;
                        ret.push_back(buff);
                        return;
                    }
                    else if(dp[i+1][len-1])
                        dfs(ret,cnt+1,i+1,str,buff,len,dict);
                }
            }
    }
    vector<string> wordBreak(string s, unordered_set<string>& dict) {
        char buff[1024];
        const int len = s.length();
        for(int i = 0 ; i < len ; i++)
            for(int j  = 0,ij=i; ij < len ; j++,ij++)
                {
                    dp[j][ij] = dict.count(s.substr(j,i+1));
                    for(int k = j; k < ij && !dp[j][ij]; k++)
                        dp[j][ij] = dp[j][k] & dp[k+1][ij];
                }
        vector<string> ret;
        dfs(ret,0,0,s,buff,s.length(),dict);
        return ret;
    }
};

Complexity Analytics

  • Time Complexity:
  • Space Complexity: