首页 > 代码库 > Word Break II

Word Break II

2024-07-06 10:52:13   221人阅读

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:
    vector<string> wordBreak(string s, unordered_set<string> &dict) 
    {
        vector<string> result;
        if(check(s,dict)==false) return result;
        
        int v[s.length()+1];v[0]=0;
        generate(result,s,dict,v,1);
        return result;
    }
    bool check(string s, unordered_set<string> &dict) 
    {
        bool able[s.length()+1];
        able[0]=true;
        for(int i=1;i<=s.length();i++)
        {
            able[i]=false;
            for(int j=0;j<i;j++)
            if(able[j] && dict.find(s.substr(j,i-j))!=dict.end())
            {
                able[i]=true;
                continue;
            }
        }
        
        return able[s.length()];
    }
    void generate(vector<string>& result,const string& s,const unordered_set<string> &dict,int* v,int vdep)
    {
        if(v[vdep-1]==s.length())
        {
            string snew=s.substr(0,v[1]);
            for(int i=2;i<vdep;i++)
            {
                snew=snew+" "+s.substr(v[i-1],v[i]-v[i-1]);
            }
            result.push_back(snew);
            return;
        }
        for(int i=1;i<=s.length()-v[vdep-1];i++)
            if(dict.find(s.substr(v[vdep-1],i))!=dict.end())
            {
                v[vdep]=v[vdep-1]+i;
                generate(result,s,dict,v,vdep+1);
            }
    }
};

 


联系
我们