41 lines
1.1 KiB
C++
41 lines
1.1 KiB
C++
#include "s0131_palindrome_partitioning.hpp"
|
|
|
|
bool isPalindrome(const string &s, int begin, int end) {
|
|
for (int i = begin, j = end; i <= j; ++i, --j) {
|
|
if (s[i] != s[j]) return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/**
|
|
* @brief 回溯
|
|
*
|
|
* @param path 每个元素都是一个回文串
|
|
* @param result 存放最终结果
|
|
* @param s 待处理的字符串
|
|
* @param startIndex s[0...startIndex - 1] 被分成了很多个子字符串,存放在 path 中
|
|
*/
|
|
void partitionDFS(vector<string> &path, vector<vector<string>> &result, const string &s, int startIndex) {
|
|
int len = s.length();
|
|
// 终止条件
|
|
if (startIndex == len) {
|
|
result.push_back(path);
|
|
}
|
|
|
|
for (int i = startIndex; i < len; ++i) {
|
|
// 如果 s[startIndex...i] 是回文串,则进入下一层
|
|
if (isPalindrome(s, startIndex, i)) {
|
|
path.push_back(s.substr(startIndex, i - startIndex + 1));
|
|
partitionDFS(path, result, s, i + 1);
|
|
path.pop_back();
|
|
}
|
|
}
|
|
}
|
|
|
|
vector<vector<string>> S0131::partition(string s) {
|
|
vector<vector<string>> result{};
|
|
vector<string> path{};
|
|
partitionDFS(path, result, s, 0);
|
|
return result;
|
|
}
|