目录
一、题目描述
二、方法1、回溯法+每次暴力判断回文子串
三、方法2、动态规划+回溯法
一、题目描述
分割回文子串
131. Palindrome Partitioning
二、方法1、回溯法+每次暴力判断回文子串
class Solution {vector<vector<string>> res;vector<string> path;
public:vector<vector<string>> partition(string s) {backtracking(s,0);return res;}void backtracking(string &s,int start){if(start == s.size()){res.push_back(path);return;}for(int i = start;i < s.size();i++){string cur = s.substr(start,i-start+1);if(!isPalindrome(cur))continue;path.push_back(cur);backtracking(s,i+1);path.pop_back();}}bool isPalindrome(const string &str){int left = 0;int right = str.size()-1;while(left<=right){if(str[left]!= str[right])return false;left++;right--;}return true;}
};三、方法2、动态规划+回溯法
先用动态规划法，求出s[i,j]是否是回文子串，后面直接查表判断回文子串。
参考leetcode 647. Palindromic Substrings-CSDN博客
class Solution {vector<vector<string>> res;vector<string> path;vector<vector<bool>> dp;
public:vector<vector<string>> partition(string s) {int n = s.size();//0 <= i<=j <= n-1//dp[i][j]表示s[i,j]是否是回文子串,其中i<=j,i>j的dp[i][j]不定义dp.resize(n,vector<bool>(n,false));for(int i = n-1;i>=0;i--){for(int j = i;j<n;j++){if(s[i] == s[j]){if(j-i <= 1){dp[i][j] = true;}else if(dp[i+1][j-1] == true){dp[i][j] = true;}}}}backtracking(s,0);return res;}void backtracking(string &s,int start){if(start == s.size()){res.push_back(path);return;}for(int i = start;i < s.size();i++){string cur = s.substr(start,i-start+1);// if(!isPalindrome(cur))// continue;if(!dp[start][i])continue;path.push_back(cur);backtracking(s,i+1);path.pop_back();}}// bool isPalindrome(const string &str){// int left = 0;// int right = str.size()-1;// while(left<=right){// if(str[left]!= str[right])// return false;// left++;// right--;// }// return true;// }
};
)
)