A solution adapted from Word Break I


  • 0
    A

    I record the preview split positions at each position using a vector.

    class Solution {
        public:
            void collect(vector<vector<int>> &splitPoints,string &s,int tail,string tail_string, vector<string> &ret)
            {
                if(tail==0)
                {
                    ret.push_back(tail_string);
                    return;
                }
                for(int index=0;index<splitPoints[tail].size();index++)
                {
                     string newtail=s.substr(splitPoints[tail][index],tail-splitPoints[tail][index])+" ";
                     newtail=newtail+tail_string;
                     collect(splitPoints,s,splitPoints[tail][index],newtail,ret);
                }
            }
            vector<string> wordBreak(string s, unordered_set<string> &dict) {
                vector<vector<int>> splitPoints(s.length()+1,vector<int>());
                splitPoints[0].push_back(0);
                for(int i=1;i<=s.length();i++)
                {
                    for(int j=i-1;j>=0;j--)
                    {
                        if(dict.find(s.substr(j,i-j))!=dict.end() && splitPoints[j].size()>0)
                        {
                            splitPoints[i].push_back(j);// available split positions from the current position backwards
                        }
                    }
                }
                vector<string> ret;
                for(int index=0;index<splitPoints[s.length()].size();index++)
                {
                     string tail=s.substr(splitPoints[s.length()][index],s.length()-splitPoints[s.length()][index]);
                     collect(splitPoints,s,splitPoints[s.length()][index],tail,ret);
                }
               
                return ret;
            }
        };

Log in to reply
 

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