做网站推广的难点、,做物流网站模块,友情链接推广,iis 网站建设中题目链接#xff1a;https://leetcode-cn.com/problems/palindrome-partitioning/
题目#xff1a;
给定一个字符串 s#xff0c;将 s 分割成一些子串#xff0c;使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: aab 输出: [ [a…题目链接https://leetcode-cn.com/problems/palindrome-partitioning/
题目
给定一个字符串 s将 s 分割成一些子串使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: aab 输出: [ [aa,b], [a,a,b] ]
解题报告
先dp预处理出所有所有回文串然后dfs就行了。如果没要求输出所有方案数则依旧可以O(n^2) dp出方案数。
AC代码
class Solution {
public:vectorvectorstring ans;vectorstring tmp;int length;int dp[1005][1005];void dfs(int pos, string s) {if(pos length1) {ans.push_back(tmp);return ;}for(int i pos; ilength; i) {if(dp[pos][i]) {tmp.push_back(s.substr(pos-1,i-pos1));dfs(i1,s);tmp.pop_back();}}}vectorvectorstring partition(string s) {length s.length();for(int l 1; llength; l) dp[l][l] 1;for(int l 1; llength; l) {if(s[l-1] s[l]) dp[l][l1] 1;}for(int len 3; len length; len) {for(int l 1; llen-1length; l) {int r llen-1;dp[l][r] dp[l1][r-1] (s[l-1] s[r-1]);}}dfs(1,s);return ans;}
};
