leetcode 131. Palindrome Partitioning

目录

一、题目描述

二、方法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;// }
};