My DP solution with C++


  • 0
    L
    typedef struct SOLNODE
        {
            int appending;
            string str;
            SOLNODE* next;
            SOLNODE(int n, string& s) : next(NULL), appending(n), str(s) {}
        }SOLNODE;
    public:
        vector<string> wordBreak(string s, unordered_set<string> &dict)
        {
            size_t slen = s.size();
            vector<bool> exists(slen + 1, false);
            exists[slen] = true;
            vector<string> solutions;
            vector<SOLNODE*> sol(slen + 1);
            for (int i = slen - 1; i >= 0; i--)
            {
                for (int j = i; j < slen; j++)
                {
                    string tmp(s, i, j - i + 1);
                    if (dict.find(tmp) != dict.end() && exists[j + 1])
                    {
                        if (sol[i] != NULL)
                        {
                            SOLNODE* p = sol[i];
                            while (p->next != NULL)
                            {
                                p = p->next;
                            }
                            p->next = new SOLNODE(j + 1, tmp);
                        }
                        else
                        {
                            sol[i] = new SOLNODE(j + 1, tmp);
                        }
                        exists[i] = true;
                    }
                }
            }
            string aSol;
            ParseSolution(sol, solutions, 0, aSol);
            return solutions;
        }
        void ParseSolution(vector<SOLNODE*>& sol, vector<string>& solutions, int index, string& aSol)
        {
            if (sol.begin() + index == sol.end()-1)
            {
                solutions.push_back(aSol);
                return;
            }
            vector<SOLNODE*>::iterator it = sol.begin() + index;
            SOLNODE* p = *it;
            while (p != NULL)
            {
                int tmpsize = aSol.size();
                if (tmpsize != 0)
                    aSol.push_back(' ');
                aSol.append(p->str);
                ParseSolution(sol, solutions, p->appending, aSol);
                aSol = string(aSol, 0, tmpsize);
                p = p->next;
            } 
        
        }
    

    In this problem, I use a vector of Solution nodes linked list to parse all the solutions. The first part is very similar with Word break I except for not breaking when finding a feasible way. For each feasible substring at position i, I add a node to the corresponding Solution nodes linked list. Next I parsed all the possible solutions from the vector using a DFS method.


Log in to reply
 

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