131 - Palindrome Partitioning

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Hide Tags
Backtracking
Hide Similar Problems
(H) Palindrome Partitioning II (M) Word Break

当然还是DFS，逐个取子串检查，如果该子串是回文，则进入递归，遇到结尾如果还是则 push 结果。
刚开始跑一直都是20 ms，仔细查看了一下，是先取子串，然后丢到单独的函数里检查是否为回文，再做后面的操作的，
但实际上还可以更快，那就是在原始字符串 s 里通过下标检测指定范围是否是回文，是的话再截取子串做处理。
改过之后果然直接 12 ms，40%的提升呐！

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> rst;
        vector<string> buf;
        dfs(s, 0, s.length(), buf, rst);
        return rst;
    }
   
    void dfs(string& s, int pos, int len, vector<string>& buf, vector<vector<string>>& rst)
    {
        for(int ii=pos; ii<len; ++ii)
        {
            int p1=pos, p2=ii;
            while(p1<p2 && (s[p1]==s[p2]))             //check palindrome in original string
                p1++, p2—;
            if(p1<p2)                                  //if substring is not a palindrome
                continue;

            string ss = s.substr(pos, ii-pos+1);
            buf.push_back(ss);
            if(ii==len-1)
                rst.push_back(buf);
            else
                dfs(s, ii+1, len, buf, rst);
            buf.pop_back();
        }
    }
};
12 ms.