# [leetcode] 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"]
]```

Dynamic Programming.

I used vector<vector<string>> dp[s.size()] as dynamic programming array.

dp[i] stores all the possible palindrome partitioning of s[0] ~ s[i]. So dp[s.size()] is the value we need to return finally.

dp[i] = dp[j – 1] appends s[j] ~ s[i], if string s[j] ~ s[i] is palindrome., j = from 0 to i .

dp[-1] is empty.

```class Solution {
public:
vector<vector<string>> partition(string s) {
if(s.size() == 0) return vector<vector<string>>();
vector<vector<string>> dp[s.size()];
//base condition
vector<string> vStr;
vStr.push_back(s.substr(0, 1));
dp[0].push_back(vStr);
//dynamic programmming
for(size_t i = 1; i < s.size(); i++){
for(size_t j = i; j > 0; j--){
string tmps = s.substr(j, i - j + 1);
if(isPalindrome(tmps)){
for(auto it = dp[j - 1].begin(); it != dp[j - 1].end(); it++){
//append character s[i] to dp[i - 1]
vStr = *it;
vStr.push_back(tmps);
dp[i].push_back(vStr);
}
}
}
//j == 0
string tmps = s.substr(0, i + 1);
if(isPalindrome(tmps)){
vStr.clear();
vStr.push_back(tmps);
dp[i].push_back(vStr);
}
}
return dp[s.size() - 1];
}
bool isPalindrome(string s){
//o(n)
//extreme case
if(s.size() == 1) return true;
int i, j;
if(s.size() % 2 == 0){
//even
i = s.size() / 2 - 1;
j = i + 1;
}
else{
//odd
i = s.size() / 2 - 1;
j = i + 2;
}
while(i >= 0){
if(s[i] != s[j]) return false;
i--;
j++;
}
return true;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.