C++ Non-recursive Solution


  • 0
    F
    class Solution
     {
        private:
            bool isParlindram(string& s, int startPos, int endPos)
            {
                while(endPos > startPos)
                {
                    if(s[endPos] != s[startPos])
                    {
                        return false;
                    }
                    endPos --;
                    startPos ++;
                }
        
                return true;
            }
        public:
            vector<vector<string> > partition(string s)
            {
                vector<vector<string> > rcs;
                if(s.size() == 0)
                {
                    return rcs;
                }
        
                int size = s.size();
                stack<int> startPoses;
                stack<int> endPoses;
                vector<string> subs(s.size(), "");
                int startPos = 0;
                int endPos = 0;
                int subCount = 0;
        
                while(endPos < size || !startPoses.empty())
                {
                    if(endPos < size)
                    {
                        for(; endPos < size; endPos ++)
                        {
                            if(isParlindram(s, startPos, endPos))
                            {
                                break;
                            }
                        }
        
                        if(endPos < size)
                        {
                            subs[subCount] = s.substr(startPos, endPos - startPos + 1);
                            if(endPos == size - 1)
                            {
                                vector<string> rc(subCount + 1);
                                for(int i = 0; i <= subCount; i ++)
                                {
                                	rc[i] = subs[i];
                                }
        
                                rcs.push_back(rc);
                            }else
                            {
                                startPoses.push(startPos);
                                endPoses.push(endPos + 1);
                                subCount ++;
                           }
        
                        }
        
                        startPos = endPos + 1;
                        endPos = startPos;
                    }else
                    {
                        startPos = startPoses.top();
                        startPoses.pop();
                        endPos = endPoses.top();
                        endPoses.pop();
                        subCount --;
                    }
                }
        
                return rcs;
            }
        };

Log in to reply
 

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