131. Palindrome Partitioning

problem description

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

algorithm thought

我第一次做这个题的时候，认为这是一个动态规划问题。定义了一个三维数组，保存之前的结果，用类似做最长增长子序列的方法解这个题。感觉时间复杂度应该是控制的还不错了。但是这种方法需要的 空间太多，并且每次得到结果都需要复制一遍所有的数字，太慢了。所以后面看到discuss使用回溯法做这个题。发现其实回溯法也不会太慢。确实，回溯法在这里会有重复计算是否是回文数的情况，但是相比动态规划的复制一整个数组，整个速度还是提高了。

因为重复计算的是判断回文字符的部分，其实这个和复制相比就很小。下一题我么不需要返回结果只需要返回个数，这时候用动态规划显然更好

code

class Solution {
public:
    //unordered_map<int,bool> ma;
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> tmp;
        helper(s,res,tmp,0);
        return res;
    }
    void helper(string&s,vector<vector<string>>&res,vector<string>&tmp,int begin){
        if(begin==s.size()){
            res.push_back(tmp);
        }
        for(int i=begin;i<s.size();++i){
            if(isPalindrome(s,begin,i)){
                tmp.push_back(std::move(s.substr(begin,i-begin+1)));
                helper(s,res,tmp,i+1);
                tmp.pop_back();
            }
        }
    }
    bool isPalindrome(string&s,int begin,int end){
        while(begin<end){
            if(s[begin++]!=s[end--])
                return false;
        }
        return true;
    }
};

algorithm analysis

时间复杂度应该是(n*2^n),这也是回溯法找到找到所有集合的普遍时间复杂度