Leetcode Palindrome Partitioning

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

典型的递归回溯法，当然可以利用动态规划法提高点效率。

下面是标准的递归回溯程序：

vector
  
    > partition(string s) 
	{
		vector
   
     > rs; vector
    
      tmp; storePatition(rs, tmp, s); return rs; } void storePatition(vector
     
       > &rs, vector
      
        &tmp, string &s) { if (s.empty()) { rs.push_back(tmp); return; } for (int i = 1; i <= s.length(); i++) { string a = s.substr(0, i); if (isPalindrome(a)) { tmp.push_back(a); string b = s.substr(i); storePatition(rs, tmp, b); tmp.pop_back(); } } } bool isPalindrome(string &s) { for (int i = 0, j = s.length()-1; i < j; i++, j--) { if (s[i] != s[j]) return false; } return true; }