Leetcode.131.Palindrome Partitio

题目

给定一个字符串, 输出所有可能的子字符串, 子字符串要求是回环字符串.

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

思路

首先需要一个函数判断是否是回环字符串.
然后递归分解出子字符串, 如果所有子字符串都是回环字符串, 即添加到结果.

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


void paritionRecrution(string &s, int index, vector<string> &vec, vector<vector<string>> &res) {
    if (index == s.size() && !vec.empty()) {
        res.push_back(vec);
        return;
    }

    for (int i = index; i < s.size(); i++) {
        if (isPalindrome(s, index, i)) {
            vec.push_back(s.substr(index, i - index + 1));
            paritionRecrution(s, i + 1, vec, res);
            vec.pop_back();
        }
    }
}

vector<vector<string>> partition(string s) {
    vector<vector<string>> result;
    vector<string> cur;
    if(s.empty()) return result;
    paritionRecrution(s, 0, cur, result);
    return result;
}

总结

这个递归的过程还是比较难以理解, 从最简单的示例进行分析.