[recommend for beginners]clean C++ implementation with detailed explanation


  • 0

    Although this problem is really classical, BUT I MEET THE trap for many times, here I will summary it.

     pass by reference : push_back() -> recursive-call  -> pop_back
    
     pass by value : the loop changed the variable, so the cur-variable should reset if changed at every loop 
    

    Code: help1 : pass by reference help2 : pass by value

      class Solution {
        public:
            vector<vector<string>> partition(string s) {
                vector<vector<string>> result;
                vector<string> cur;
                help2(s, cur, result, 0);
                return result;
            }
            
            void help1(const string& s, vector<string>& cur, vector<vector<string>>& result, int pos){
                if(pos==s.size())   { result.push_back(cur);  return;}
                for(int i=pos; i<s.size(); i++){
                    if(check(s, pos, i)){
                        cur.push_back(s.substr(pos, i-pos+1));
                        help(s, cur, result, i+1);
                        cur.pop_back();
                    }
                }
            }
            
            void help2(const string& s, vector<string> cur, vector<vector<string>>& result, int pos){
                if(pos==s.size())   { result.push_back(cur);  return;}
                for(int i=pos; i<s.size(); i++){
                    if(check(s, pos, i)){
                        vector<string> temp(cur);
                        temp.push_back(s.substr(pos, i-pos+1));
                        help(s, temp, result, i+1);
                    }
                }
            }
            
            bool check(const string& s, int start, int end){
                while(start<end){
                    if(s[start++]!=s[end--])    return false;
                }
                return true;
            }
        };

  • 0
    2

    2 TIMES AC solution

    class Solution {
    public:
        vector<vector<string>> partition(string s) {
            vector<vector<string>> result;
            vector<string> path;
            help(result, path, s, 0);
            return result;
        }
        
        void help(vector<vector<string>>& result, vector<string> path, string s, int pos) {
            if(pos == s.size()) {
                result.push_back(path);
                return;
            }
            for(int i = pos; i < s.size(); i++) {
                string temp = s.substr(pos, i - pos + 1);
                if(check(temp)){
                    path.push_back(temp);
                    help(result, path, s, i + 1);
                    path.pop_back();
                }
            }
        }
        
        bool check(string s) {
            int size_s = s.size();
            if(size_s <= 1)  return true;
            for(int i = 0, j = size_s-1; i < j; i++, j--) {
                if(s[i] != s[j])  return false;
            }
            return true;
        }
    };

  • 0
    A

    @RainbowSecret What trap? I don't get it. You can also write pass by value as pass by reference. e.g.

            void help2(const string& s, vector<string> cur, vector<vector<string>>& result, int pos){
                if(pos==s.size())   { result.push_back(cur);  return;}
                for(int i=pos; i<s.size(); i++){
                    if(check(s, pos, i)){
                        cur.push_back(s.substr(pos, i-pos+1));
                        help2(s, cur, result, i+1);
                        cur.pop_back();
                    }
                }
            }
    

Log in to reply
 

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