131-分割回文串

LeetCode 131. Palindrome Partitioning

LeetCode-131

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome string is a string that reads the same backward as forward.

Example 1:

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

method: 回溯

string.substr(pos, length) 截取从pos开始的length个字符

枚举每一个分割点，如果分割出来的子串string[index, i]是回文，就继续递归，否则这个分割点不行，跳到下一个分割点

vector<vector<string>> ret;
vector<string> path;
bool isPalindrome(string& s, int i, int j) {
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++;
        j--;
    }
    return true;
}
void traversal(string& s, int index) {
    if (index == s.size()) {
        ret.push_back(path);
        return;
    }
    for (int i = index; i < s.size(); ++i) {
        if (isPalindrome(s, index, i)) {    // s[index,i]
            path.push_back(s.substr(index, i - index + 1)); // 左闭右闭
            traversal(s, i + 1);
            path.pop_back();
        }
        else continue;  // 如果不是回文，就跳到下一个分割点
    }
}
vector<vector<string>> partition(string s) {
    traversal(s, 0); 
    return ret;
}