Palindrome Partitioning

Palindrome Partitioning

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

Given s = “aab”, return:
[
  [“aa”,”b”],
  [“a”,”a”,”b”]
]

分析：

深搜，用递归，同时剪枝。

思路：

  1. 依次递增第一次断开的位置，如果从第一位到断开的位置的子字符串是回文就把它放入一个vector，并将剩余子串的第一位作为起始位置，重复此步骤。
  2. 如果从第一位到断开的位置的子串不是回文，直接递增断开位置。
  3. 终止和边界条件都是：第一次断开的位置是最后一位。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdlib.h>
#include <stdint.h>
#include <vector>

using namespace std;

class Solution {
public:
    /**
    * @param s: A string
    * @return: A list of lists of string
    */
    vector<vector<string> > partition(string s) {
        // write your code here
        vector<vector<string>> rs;
        vector<string> path;

        dfs(rs, path, s, 0);

        return rs;
    }

    void dfs(vector<vector<string> > &rs, vector<string> &path, const string &s, int start) {
        if (start == s.size()) {
            rs.push_back(path);
            return;
        }

        for (int i = start; i < s.size(); i++) {
            if (isPalindrome(s, start, i)) {
                path.push_back(s.substr(start, i - start + 1));
                dfs(rs, path, s, i + 1);
                path.pop_back();
            }
        }
    }

    bool isPalindrome(const string s, int start, int end) {
        while (start < end && s[start] == s[end]) {
            start++;
            end--;
        }

        return start >= end;
    }
};