If feel this problem Complex, this piece of Readable Codes with Explanatory Notes May Help


  • 0
    B
    class Solution {
    public:
        void wordBreak_add(string &origin, vector<vector<int> > &Edges, int L, 
            string current, int curPos, vector<string> &ans )
        {
            for(int i = 0; i < Edges[curPos].size(); i ++)
            {
                int nextPos = Edges[curPos][i];
                string next = current;
                /* add a word to the current piece of string,
                    for further comprising of some valid sentences */
                if(curPos == 0)
                {
                    next = origin.substr(curPos, nextPos - curPos);
                }
                else
                {
                    next += (string(" ") + origin.substr(curPos, nextPos - curPos));
                }
                
                /* nextPos == L means you get a kind of valid sentences */
                if(nextPos == L)ans.push_back(next);
                else wordBreak_add(origin, Edges, L, next, nextPos, ans);
            } 
        }
        vector<string> wordBreak(string s, unordered_set<string> &dict) {
            vector<string> ans;
            int L=s.length();
            if(L<1)return ans;
            
            /* sig[i] == ture means:
                s.substr(i, L -i) could be a string has valid wordBreak solutions */
            bool *sig=new bool[L+5];
            memset(sig,0,L);
            
            /* Any element of Edges[curPos] nextPos means:
                s.substr(curPos, nextPos-curPos) is a word in the dictionary,
                and sig[nextPos] == true,
                from these two conditions, you can derive valid sentences.
                Especially, when nextPos == L, then you get a kind of whole valid sentences.*/
            vector<vector<int> > Edges;
            for(int i = 0; i < L; i ++)Edges.push_back(vector<int>());
            
            /* Do dynamic programming from the back,
                sig[0] == true means the original string s has valid wordBreak solutions */
            for(int i = L-1; i >= 0; i --)
            {
                if(dict.find(s.substr(i, L-i)) != dict.end())
                {
                    sig[i] = true;
                    Edges[i].push_back(L);
                }
                if(sig[i])
                {
                    for(int j = i-1; j >= 0; j --)
                    {
                        if(dict.find(s.substr(j,i-j)) != dict.end()){
                            Edges[j].push_back(i);
                            sig[j] = true;
                        }
                    }
                }
            }
            
            if(!sig[0])
            {
                delete[] sig;
                return ans; //no valid solution
            }
            
            delete[] sig;
            /* Use recursive function to derive all the solutions,
                the complexity is unavoidable, since all the solutions must be made.*/
            wordBreak_add(s, Edges, L, string(), 0, ans);
            return ans;
        }
    };

Log in to reply
 

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