Concise c++ traceback solution


  • 0
    W
        class Solution {
    public:
        vector<vector<string>> res;
        vector<vector<string>> partition(string s) {
            vector<vector<int>> ispal(s.length(),vector<int>());
            for(int i = 0; i < s.length(); i++){
                for(int j = 0;i-j>=0&&i+j<s.length()&&s[i-j]==s[i+j];j++)
                ispal[i-j].push_back(i+j);
                for(int j = 1;i-j+1>=0&&i+j<s.length()&&s[i-j+1]==s[i+j];j++)
                ispal[i-j+1].push_back(i+j);
            }
            vector<string> tmp;
            traceback(s,ispal,tmp,0);
            return res;
        }
        void traceback(string s, vector<vector<int>> &ispal,vector<string> &tmp, int index){
            if(index == s.length()){
            res.push_back(tmp);
            return;
            }
            vector<int> ilist = ispal[index];
            for(int i = 0; i < ilist.size(); i++){
                int end = ilist[i];
                tmp.push_back(s.substr(index,end-index+1));
                traceback(s,ispal,tmp,end+1);
                tmp.pop_back();
            }
        }
    };
    

    ispal[i] is a vector used to store all the destination index j from i so that s.substr(i,j-i+1) is palindrome.


Log in to reply
 

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