standard and easy C++ backtracking solution No DP


  • 0
    R

    The idea using DP is that we may get TLE for some weird and long test cases, which is meaningless. As a result, I will do a word break I to check those cases.

    class Solution {
    public:
        vector<string> wordBreak(string s, vector<string>& wordDict) {
            vector<string> res;
            if(wordBreak1(s,wordDict)==false) return res;
            unordered_set<string> Dict(wordDict.begin(),wordDict.end());
            dfs(s,0,res,"",Dict);
            return res;
        }
        
        void dfs(string s, int idx, vector<string>& res, string sub, unordered_set<string>& dict){
            if(idx==s.size()){
                res.push_back(sub.substr(0,sub.size()-1));
                return;
            }
            for(int i=idx;i<s.size();i++){
                string word = s.substr(idx,i-idx+1);
                if(dict.find(word) != dict.end()){
                    sub+=word;
                    sub+=" ";
                    int size= word.size()+1;
                    dfs(s,i+1,res,sub,dict);
                    for(int k=0;k<size;k++) sub.pop_back();
                }
            }
            return;
        }
        
        
        
        
        
        bool wordBreak1(string s, vector<string>& wordDict) {
            unordered_set<string> worddict(wordDict.begin(),wordDict.end());
            vector<bool> dp(s.size()+1,false);
            dp[0]=true;
            for(int i=1;i<=s.size();i++)
            {
                for(int j=0;j<i;j++){
                    if(dp[j] and worddict.count(s.substr(j,i-j))) dp[i]=true;
                }
            }
            return dp[s.size()];
        }
    };
    

Log in to reply
 

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