首页 > 代码库 > 【leetcode】Palindrome Partitioning

【leetcode】Palindrome Partitioning

2024-08-10 07:34:31   216人阅读

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [    ["aa","b"],    ["a","a","b"]  ]
为了加速运算，可以利用动态规划，求出满足回文的子串的位置
 
palindrome[i][j]表示了第字符串中，s[i,i+1,……, j]是否是回文
 
可以有以下递推公式：
if(i==j) palindrome[i][j]=true;
if(i-j=1)palindrome[i][j]=s[i]==s[j];
if(i-j>1)palindrome[i][j]=palindrome[i+1][j-1]&&s[i]==s[j]
 
 
得到了该回文表后，我们利用回溯法得到所有的子串
 
 
 
 1 class Solution { 2 public: 3   4     vector<vector <string> > res; 5     6     vector<vector<bool> > palindrome; 7     string s; 8     int n; 9    10     vector<vector<string>> partition(string s) {11        12          this->s=s;13          this->n=s.length();14          15          vector<vector<bool> > palindrome(n,vector<bool>(n));16          getPalindrome(palindrome);17          this->palindrome=palindrome;18          19          vector <string> tmp;20          getPartition(0,tmp);21          22          return res;23     }24    25     //回溯得到子串26     void getPartition(int start,vector<string> tmp)27     {28  29         if(start==n)30         {31             res.push_back(tmp);32             return;33         }34        35         for(int i=start;i<n;i++)36         {37             if(palindrome[start][i])38             {39                 tmp.push_back(s.substr(start,i-start+1));40                 getPartition(i+1,tmp);41                 tmp.pop_back();42             }43         }44     }45    46    47    48     void getPalindrome(vector<vector<bool> > &palindrome)49     {50         int startIndex=0;51         int endIndex=n-1;52        53         for(int i=n-1;i>=0;i--)54         {55             for(int j=i;j<n;j++)56             {57                 if(i==j)58                 {59                     palindrome[i][j]=true;60                 }61                 else if(j-i==1)62                 {63                     palindrome[i][j]=(s[i]==s[j]);64                 }65                 else if(j-i>1)66                 {67                     palindrome[i][j]=(s[i]==s[j]&&palindrome[i+1][j-1]);68                 }69             }70         }71     }72 };

 

【leetcode】Palindrome Partitioning


联系
我们