My solution in c++


  • 0
    S
    class Solution {
    public:
    void DFS(const string & s, vector<pair<vector<string>,bool>> & f,const unordered_set<string> & dict,int index, const int n){
    	if(f[index].second==true) return;
    	f[index].second = true;
    	for(int i = index; i!=n; ++i){
    		string cur_substr = s.substr(index,i-index+1);
    		if(dict.find(cur_substr)!=dict.end()){
    			if(i+1==n) f[index].first.push_back(cur_substr);
    			else{
    				DFS(s,f,dict,i+1,n);
    				for(int j = 0; j!=f[i+1].first.size(); ++j){
    					string tmp = cur_substr;
    					tmp.append(" ");
    					tmp.append(f[i+1].first[j]);
    					f[index].first.push_back(tmp);
    				}
    			}
    		}
    	}
    }
    
    vector<string> wordBreak(string s, unordered_set<string> &dict){
    	const int n = s.size();
    	vector<pair<vector<string>,bool>> f (n,make_pair(vector<string>(),false));
    	DFS(s,f,dict,0,n);
    	return f[0].first;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.