首页 > 代码库 > Palindrome Partitioning

Palindrome Partitioning

2024-07-17 07:41:30   221人阅读

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"]  ]

思路：先使用DP确定s中任意两个字符之间是否构成回文。若isPalindrome[step][i]为true，则表示str.substr(i,step+i)构成回文。

        然后，使用DFS求解出所有合法划分。

 1 class Solution { 2 public: 3     vector<vector<string>> partition( string s ) { 4         if( s.empty() ) { return palindromes; } 5         size = s.length(); str = s; 6         vector<bool> *isPalindrome = new vector<bool>[size]; 7         isPalindrome[0].resize( size, true ); 8         for( size_t step = 1; step != size; ++step ) { 9             isPalindrome[step].resize( size-step, false );10             if( step == 1 ) {11                 for( size_t i = 0; i != size-1; ++i ) {12                     if( s[i] == s[i+1] ) { isPalindrome[1][i] = true; }13                 }14             } else {15                 for( size_t i = 0; i != size-step; ++i ) {16                     if( s[i] == s[i+step] && isPalindrome[step-2][i+1] ) { isPalindrome[step][i] = true; }17                 }18             }19         }20         vector<string> palindrome;21         GeneratePalindromes( palindrome, 0, isPalindrome );22         delete [] isPalindrome;23         return palindromes;24     }25 private:26     void GeneratePalindromes( vector<string>& palindrome, int index, vector<bool>* isPalindrome ) {27         if( index >= size ) { palindromes.push_back( palindrome ); return; }28         for( int step = 0; step < size-index; ++step ) {29             if( isPalindrome[step][index] ) {30                 string subStr = str.substr( index, step+1 );31                 palindrome.push_back( subStr );32                 GeneratePalindromes( palindrome, index+step+1, isPalindrome );33                 palindrome.pop_back();34             }35         }36         return;37     }38     int size;39     string str;40     vector<vector<string>> palindromes;41 };

另外，笔者发现使用vector<bool> *isPalindrome = new vector<bool>[size]会比使用vector<vector<bool>> isPalindrome(size)稍微快一些，这相当于用size个小的存储块取代了原来的大的存储块。不过，这么做需要添加delete [] isPalindrome释放掉new出的空间。


联系
我们