Clean C++ backtracking solution


  • 54
    Z

    The Idea is simple: loop through the string, check if substr(0, i) is palindrome. If it is, recursively call dfs() on the rest of sub string: substr(i+1, length). keep the current palindrome partition so far in the 'path' argument of dfs(). When reaching the end of string, add current partition in the result.

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

  • 0
    A

    My idea is the same as yours, but my code is in python. I have tried your code in C++, the runnning time is only 19ms. But the running time of my python code is near 200ms. The gap of C++ and python is so big on running efficiency.


  • 0
    W

    I think it depends on the specific configuration on the test band which is tricky measuring in ms.


  • 3

    Similar idea based on your solution, but without the need of using "index".

    bool isPalindrome(const string &s) {
      int i = 0;
      int j = s.size() - 1;
    
      while (i < j) {
        if (s[i] != s[j])
          return false;
        i ++;
        j --;
      }
    
      return true;
    }
    
    void partition(string s, vector<string> &cur, vector<vector<string> > &total) {
      if (s.size() <= 0)
        return;
    
      if (isPalindrome(s)) {
        cur.push_back(s);
        total.push_back(cur);
        cur.pop_back();
      }
    
      for (int i = 1; i < s.size(); ++ i) {
        string cur_str = s.substr(0, i);
        if (isPalindrome(cur_str)) {
          cur.push_back(cur_str);
          partition(s.substr(i, s.size() - i), cur, total);
          cur.pop_back();
        }
      }
    }
    
    vector<vector<string> > partition(string s) {
      vector<vector<string> > total;
      vector<string> cur;
      partition(s, cur, total);
      return total;
    }
    

  • 0

    Really nice recursion, thanks


  • 2
    C

    So is the time complexity O(n * 2^n)?
    My thought is, in the worst case (i.e. "aa...aa") there are O(2^n) kind of partition configuration, and each configuration takes O(n) to check isPalindrome.


  • 1
    M

    Have exactly same solution as yours :)

    class Solution {
    public:
        bool isPalindrome(string s) {
            int left = 0, right = s.length()-1;
            while(left <= right) {
                if (s[left] != s[right]) {
                    return false;
                }
                else {
                    left++;
                    right--;
                }
            }
            return true;
        }
        void loadResult(vector<vector<string>>& result, vector<string>& tempResult, int start, string& s) {
            if (start == s.length()) {
                result.push_back(tempResult);
            }
            else {
                string palin = "";
                for (int i = start; i < s.length(); i++) {
                    palin += s[i];
                    if (isPalindrome(palin)) {
                        tempResult.push_back(palin);
                        loadResult(result, tempResult, i+1, s);
                        tempResult.pop_back();
                    }
                }
            }
        }
        vector<vector<string>> partition(string s) {
            vector<vector<string>> result;
            vector<string> tempResult;
            loadResult(result,tempResult,0,s);
            return result;
        }
    };
    

  • 0
    A

    @cheyuanl How are you able to determine that there are 2^n partition configurations. Sorry, I'm not too familiar with time complexity for recursion, but any help is appreciated


  • 0
    B

    Check if substr is palindrome can be done in O(1) with pre-calculated hash value.

    vector<vector<string>> partition(string s) {
        int len=s.length();
        if(len==0)
            return vector<vector<string>> ();
        vector<unsigned long long> hs1(s.length()+2, 0), hs2(s.length()+2, 0), pw(s.length()+1, 1);
        for(int i=0, j=len-1; i<s.length(); ++i, --j){
            hs1[i+1]=hs1[i]*31+s[i]-'a'+1;
            pw[i+1]=pw[i]*31;
            hs2[j+1]=hs2[j+2]*31+s[j]-'a'+1;
        }
        vector<vector<string>> ans;
        vector<string> v;
        solve(s, 0, v, ans, hs1, hs2, pw);
        return ans;
    }
    bool isp(string &s, int l, int r, vector<unsigned long long> &hs1, vector<unsigned long long> &hs2, vector<unsigned long long> &pw){
        int mid=(l+r)/2;
        if((l+r)%2==0){
            return hs1[mid+1]-hs1[l]*pw[mid-l+1]==hs2[mid+1]-hs2[r+2]*pw[mid-l+1];
        }else{
            return hs1[mid+1]-hs1[l]*pw[mid-l+1]==hs2[mid+2]-hs2[r+2]*pw[mid-l+1];
        }
    }
    void solve(string &s, int cur, vector<string> &v, vector<vector<string>> &ans, vector<unsigned long long> &hs1, vector<unsigned long long> &hs2, vector<unsigned long long> &pw){
        if(cur==s.length()){
            ans.push_back(v);
            return;
        }
        for(int k=0; cur+k<s.length(); ++k){
            if(isp(s, cur, cur+k, hs1, hs2, pw)){
                v.push_back(s.substr(cur, k+1));
                solve(s, cur+k+1, v, ans, hs1, hs2, pw);
                v.pop_back();
            }
        }
    }

  • 0
    D

    Mine is a little bit optimized, like regular DP, use a unordered_map to keep track of all palindrome tests we've done, e.g. unorder_map[(1,2)] is false means substring from index 1 to 2 is not palindrome. whenever I do a palindrome test, I put its result in the map, and whenever I need to do a palindrome test, I check the map first.

    There is one caveat, that STL hash does not take std::pair as key, unordered_map<pair<int, int>, bool> does not compile, so I changed it to unordered_map<int, bool>, where int is a unique value from start and end, e.g. start * 997 + end. kinda double hash. All tests passed, but the key hash can be updated to fit more complicated situations.


  • 0
    D

    @dengydongn, or define a comparer for pair


Log in to reply
 

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