Leetcode--Word Break II

Problem Description:

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

代码如下：

class Solution {
public:
    
    void dfs(string &s, int begin, int len, unordered_set<string> &dict, 
    vector<bool> &flag, string &str, vector<string> &res)
    {
        if(begin==len)
        {
            res.push_back(str.substr(1));
            return;
        }
        
        for(int i=begin;i<len;++i)
        {
            string substring=s.substr(begin,i-begin+1);
            if(dict.count(substring)==1&&flag[i+1])
            {
                str+=" "+substring;
                dfs(s,i+1,len,dict,flag,str,res);
                str.resize(str.size()-substring.size()-1);
            }
        }
        
    }
    
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> res;
        string str;
        if(s.size()==0)
            return res;
        int len=s.size();
        vector<bool> flag(len+1,false);
        flag[len]=true;
        
        for(int i=len-1;i>=0;--i)
            for(int j=len;j>i;--j)
            {
                if(flag[j]&&dict.count(s.substr(i,j-i))==1)
                {
                    flag[i]=true;
                    break;
                }
            }
            
        dfs(s,0,len,dict,flag,str,res);
        return res;

    }
};

Leetcode--Word Break II,布布扣,bubuko.com

Leetcode--Word Break II

原文：http://blog.csdn.net/longhopefor/article/details/23341589