9ms Classic backtracking solution combined with Wordbreak I


  • 0
    J
    class Solution {
    public:
        vector<string> wordBreak(string s, vector<string>& wordDict) {
            vector<string> ans;
            string cur="";
            int len=s.size();
            if(len==0)
                return ans;
            unordered_set<string> st;
            for(auto word:wordDict)
            {
                st.insert(word);
            }
            vector<bool> dp(len+1, false);
            if(breakable(dp, s, st))
                help(s, 0, st, cur, ans, dp);
            return ans;
        }
        
        bool  breakable(vector<bool>& dp, string& s, unordered_set<string>& st)
        {
            dp[0]=true;
            int len=dp.size();
            for(int i=1; i<len; i++)
            {
                for(int j=i-1; j>=0; j--)
                {
                    if(dp[j])
                    {
                        string sub=s.substr(j, i-j);
                        if(st.find(sub) != st.end())
                        {
                            dp[i]=true;
                        }
                    }
                }
            }
            return dp[len-1];
        }
        void help(string s, int pos, unordered_set<string>& st, string& cur, vector<string>& ans, vector<bool>& dp)
        {
            if(pos >= s.size())
            {
                cur=cur.substr(0, cur.size()-1);
                ans.push_back(cur);
                cur.clear();
                
                return;
            }
            
           
            for(int i=1; i<=s.size()-pos; i++)
            {
                string sub=s.substr(pos, i);
                if(dp[pos+i]==true && st.find(sub) != st.end())
                {
                    string saved=cur;
                    cur+=sub+" ";
                    help(s, pos+i, st, cur, ans, dp);
                    cur=saved;
                }
            }
        }
    };
    

Log in to reply
 

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