分割回文串

LeetCode 131 · Medium · 1 min · 榎aaaa

思路：对于每一个字符，都先判断其是否能够被分割，即以start为首，以当前字符为尾的字符串是否为回文串；如果能够分割（第一条路径），就将当前元素压入path，组成子回文串，并从下一个字符开始进行新一轮的回文串判断；第二条路径为：不从当前字符进行分割，而是直接转向下一个字符，从下一个字符开始判断（为了找到更长的回文串）

 1bool isPalindrome(const string& s, int left, int right)
 2{
 3    while(left < right)
 4    {
 5        if(s[left++] != s[right--])
 6            return false;
 7    }
 8    return true;
 9}
10void dfs(string& s, int index, int start, vector<string>& path, vector<vector<string>>& res)
11{
12    const int sz = s.size();
13    if(index == sz)
14    {
15        res.emplace_back(path);
16        return;
17    }
18
19    if(isPalindrome(s, start, index))
20    {
21        path.emplace_back(s.substr(start, index - start + 1));
22        dfs(s, index + 1, index + 1, path, res);
23        path.pop_back();
24    }
25
26    if(index < sz - 1)
27        dfs(s, index + 1, start, path, res);
28}
29
30vector<vector<string>> partition(string s)
31{
32    vector<string> path;
33    vector<vector<string>> res;
34
35    dfs(s, 0, 0, path, res);
36    return res;
37}