Shared my clean easy to understand C++ solution


  • 1
    R

    I shared my code, which should be pretty clear to understand, I wonder if someone could tell me the space and time complexity, I found it hard to figure out space and time complexity for recursive solutions, thanks in advance

    class Solution {
    public:
        vector<vector<string>> partition(string s) {
            vector<string> result;
            vector<vector<string>>results;
            partition(s, 0, result, results);
            return results;
        }
    private:
        void partition(string&s,int start,vector<string>&result,
                       vector<vector<string>>&results){
            if(start==s.size()) {
                results.push_back(result);
                return;
            }               
            for(int i=start; i<s.size(); ++i) {
                string word=s.substr(start, i-start+1);
                if(isPalindrome(word)) {
                    result.push_back(word);
                    partition(s, i+1, result, results);
                    result.pop_back();
                }
            }
        }
        bool isPalindrome(string s) {
            int start=0, end=s.size()-1;
            while(start<end) {
                if(s[start]!=s[end]) return false;
                start++; end--;
            }
            return true;
        }
    };

Log in to reply
 

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