LeetCode OJ:Word Break II

Word Break II  
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"] .
アルゴリズムの考え方:
iからjが辞書に存在するか否かをdp[i][j]で保存し、dpに基づいて文字列を再帰的に構築する
考え方は簡単ですが、前から後に文字列を再帰的に構築する場合は、私が初めて書いた再帰コードなどに注意する必要があります.

void dfs(int k, string &s){
		
		if(k==length){
			string str;
			for(int i=0;i<t.size();i++){
				if(i!=0)
					str.push_back(' ');
				str += t[i];
			}
			result.push_back(str);
			return;
		}
		for(int i=0;i<length-k;i++){
			if(dp[k][i]){
				t.push_back(s.substr(k,i+1));
				dfs(k+i+1,s);
				t.pop_back();
			}
		}
	}

最後のテストデータを提出すると常にタイムアウトになるので、後から前へ再帰し、再帰回数を減らさなければなりません.

void dfs(int k, string &s){
		if(k==-1){
			string str;
			for(int i=t.size()-1;i>=0;i--){
				str += t[i];
				if(i!=0)
					str.push_back(' ');
			}
			result.push_back(str);
			return;
		}
		for(int i=0;i<=k;i++){
			if(dp[i][k-i]){
				t.push_back(s.substr(i,k-i+1));
				dfs(i-1,s);
				t.pop_back();
			}
		}
	}

ACのコードは次のとおりです.

class Solution{
public:
	vector<string> result;
	vector<vector<bool>> dp;
	vector<string> t;
	int length;
	void dfs(int k, string &s){
		if(k==-1){
			string str;
			for(int i=t.size()-1;i>=0;i--){
				str += t[i];
				if(i!=0)
					str.push_back(' ');
			}
			result.push_back(str);
			return;
		}
		for(int i=0;i<=k;i++){
			if(dp[i][k-i]){
				t.push_back(s.substr(i,k-i+1));
				dfs(i-1,s);
				t.pop_back();
			}
		}
	}
	vector<string> wordBreak(string s, unordered_set<string> &dict) {
		length=s.size();
		dp.resize(length);
		for(int i=0;i<length;i++){
			for(int j=i;j<length;j++)
				dp[i].push_back(dict.count(s.substr(i,j-i+1)));
		}
		dfs(length-1,s);
		return result;
	}
};

動的計画:

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<bool> f(s.length()+1,false);
        //prev[i][j]=true  s[j,i)       ，   j   
        vector<vector<bool>> prev(s.length()+1,vector<bool>(s.length()));
        f[0]=true;
        for(size_t i=1;i<=s.length();++i){
            for(int j=i-1;j>=0;--j){
                if(f[j]&&dict.find(s.substr(j,i-j))!=dict.end()){
                    f[i]=true;
                    prev[i][j]=true;
                }
            }
        }
        vector<string> result;
        vector<string> path;
        gen_path(s,prev,s.length(),path,result);
        return result;
    }
private:
    void gen_path(const string &s,const vector<vector<bool>> &prev,int cur,
                    vector<string> &path,vector<string> &result){
        if(cur==0){
            string tmp;
            for(auto iter=path.crbegin();iter!=path.crend();++iter)
                tmp+=*iter+" ";
            tmp.erase(tmp.end()-1);
            result.push_back(tmp);
            return;
        }
        for(size_t i=0;i<s.size();++i){
            if(prev[cur][i]){
                path.push_back(s.substr(i,cur-i));
                gen_path(s,prev,i,path,result);
                path.pop_back();
            }
        }
    }
};