8ms C++ solution, beat 93%, easy to understand


  • 0
    P
    class Solution {
    public:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            vector<string> res;
            int N = s.size();
            vector<bool> dp(N+1,false);
            dp[0] = true;
            for(int i=1;i<=N;i++){
                for(int j=i-1;j>=0;j--){
                    if(!dp[j])  continue;
                    string t = s.substr(j,i-j);
                    if(wordDict.count(t)==0)    continue;
                    dp[i] = true;
                    break;
                }
            }
            if(dp[N] == false)  return res;
            string tmp;
            dfs(s,wordDict,tmp,res,dp,0);
            return res;
        }
        void dfs(string s,unordered_set<string>& wordDict,string tmp,vector<string> &res,vector<bool> &dp,int start){
            if(start>=s.size()){
                tmp.erase(tmp.end()-1,tmp.end());
                res.push_back(tmp);
            }
            for(int i=start;i<s.size();i++){
                if(!dp[i+1])    continue;               
                string t = s.substr(start,i-start+1);   
                if(wordDict.count(t)==0)	continue;   
                dfs(s,wordDict,tmp+t+" ",res,dp,i+1);
            }
        }
    };
    

Log in to reply
 

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