Backtrack and bit manipulation

131. Palindrome Partitioning

For this problem, we can put a separate after the position i or not put a separate. In total, we will have 2^(n-1) cases to put the separators.

We can solve it by using

• backtrack
• bit manipulation

The time complexity is:

O(n * 2^n ) where O(n) is used for checking whether the string after sepration is palindrome. O(2^n) is number of ways to separating.

Backtrack

class Solution {
    public:
    void backtrack(string& s,int i, vector<string>& current,vector<vector<string>>& ret){
        const int n = s.size();
        // touch the bottom of the backtracking
        if (i == n){
            if (is_palindrome(current.back())){
                ret.push_back(current);
            }
            return;
        }
        // put a separate at position i
        if (is_palindrome(current.back())){
            current.push_back(s.substr(i, 1));
            backtrack(s, i + 1, current, ret);
            if (current.back().size() > 1){
                current.back().pop_back();
            } else {
                current.pop_back();
            }
        }
        // do not put a separate at position i
        current.back().push_back(s[i]);
        backtrack(s, i + 1, current, ret);
        if (current.back().size() > 1){
            current.back().pop_back();
        } else {
            current.pop_back();
        }
}
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ret;
        vector<string> current;
        current.push_back(s.substr(0, 1));
        if (s.size() == 0) return ret;
        if (s.size() == 1) {
            ret.push_back({s});
            return ret;
        }
        int i = 1;
        backtrack(s, i, current, ret);
        return ret;
}
    private:
    bool is_palindrome(string& c){
        const int n = c.size();
        if (n <= 1)return true;
        int i = 0, j = n - 1;
        while (i < j){
            if (c[i++] != c[j--])return false;
        }
        return true;
    }
};

Bit Manipulation

class Solution {
public:
  
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ret;
        const int n = s.size() - 1;
        for (int i = 0; i < (1 << n); ++i){
            vector<string> candidate = _partition(s, i);
            if(are_palindromes(candidate)){
                ret.push_back(candidate);
            }
        }
        return ret;
        
    }
    private:
    bool is_palindrome(string& c){
        const int n = c.size();
        if (n <= 1)return true;
        int i = 0, j = n - 1;
        while (i < j){
            if (c[i++] != c[j--])return false;
        }
        return true;
    }
    bool are_palindromes(vector<string>&candidate){
        if (candidate.empty())return true;
        for (auto & c: candidate){
            if (!is_palindrome(c))return false;
        }
        return true;
    }
      vector<string> _partition(string s,int mask){
          const int n = s.size();
          vector<string> ret;
          string curr = "";
          for (int i = 0; i < n; ++i){
              curr += s[i];
              if ((1 << i) & mask){
                  ret.push_back(curr);
                  curr = "";
              }
          }
          ret.push_back(curr);
          return ret;
      }
};