Can someone please help me to find the complexity of my code? thanks a lot


  • 0
    R

    The solution should be clean, but always hard to figure out recursive complexity for me, thanks a lot

    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.