c++ backtracing solution


  • 0
    H
    class Solution {
    public:
        vector<vector<string>> ans;
        bool isPalindrome(string s, int start, int end) {
            while(start < end) {
                if(s[start] != s[end]) return false;
                start ++;
                end --;
            }
            return true;
        }
        void search(string s, int start, int end, vector<string> cur) {
            if(end >= s.size()) return;
            if(isPalindrome(s, start, end)) {
                cur.push_back(s.substr(start, end - start + 1));
                if(end == s.size()-1) {
                    ans.push_back(cur);
                    return;
                }
                else {
                    search(s, end+1, end+1, cur);
                    cur.pop_back();
                }
            }
            search(s, start, end+1, cur);
        }
        vector<vector<string>> partition(string s) {
            int n = s.size();
            if(!n) return ans;
            search(s, 0, 0, vector<string> (0));
            return ans;
        }
    };
    

Log in to reply
 

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