# C++ Summary of all Palindrome Problem Set

• Firstly, let us check the Manacher Algorithm You can check the previous link to grasp it, in fact, it is not hard to understand. Its idea is easy to grasp.

``````string Manacher(string s) {
//start use \$ char
string t = "\$#";
for (int i = 0; i < s.size(); i++) {
t += s[i];
t += "#";
}
vector<int> p(t.size(), 0);
int mx = 0, id = 0, resLen = 0, resCenter = 0;
for (int i = 1; i < t.size(); i++) {
p[i] = mx > i ? min(p[2*id - i], mx - i) : 1;
while (t[i + p[i]] == t[i-p[i]]) ++p[i];
if (mx < i + p[i]) {
mx = i + p[i];
id = i;
}
if (resLen < p[i]) {
resLen = p[i];
resCenter = i;
}
}
return s.substr((resCenter - resLen) / 2, resLen - 1);
}
``````

Let us quickly check all the 9 palindrome problem set in leetcode :

Palindrom Number Check

``````class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) return false;
int div = 1;
while (x / div >= 10) div *= 10;
while (x > 0) {
int left = x / div;
int right = x % 10;
if (left != right) return false;
x = (x % div) / 10;
div /= 100;
}
return true;
}
};

``````

Palindrome String Check
We need to skip all the invalid chars !

``````class Solution {
public:
bool isPalindrome(string s) {
int len=s.size();
if(len<=1)  return true;
int left=0, right=len-1;
while(left<right){
while(left<right && !check(s[left])) left++;
while(right>left && !check(s[right])) right--;
// if(left==len || right==-1)  return true;
if(toupper(s[left])!=toupper(s[right]))  return false;
left++;
right--;
}
return true;
}

bool check(char c){
return (c>='a' && c<='z') || (c>='A' && c<='Z') || (c>='0' && c<='9');
}
};

``````

Palindrome Partitioning 1

``````
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> curPath;
dfs(s,curPath,result);
return result;
}
void dfs(string s, vector<string>& curPath, vector<vector<string>>& result) {
if (s.size() == 0) {
result.push_back(curPath);
return;
} else {
for (int i = 1; i <= s.size(); i ++) {
string curWord = s.substr(0,i);
string nextWord = s.substr(i);
if (isPalindrome(curWord)) {
curPath.push_back(curWord);
dfs(nextWord, curPath, result);
curPath.pop_back();
}
}
}
}

bool isPalindrome(string s) {
int start = 0, end = s.size() - 1;
while (start  < end) {
if (s[start] == s[end]) {
start ++;
end --;
} else {
return false;
}
}
return true;
}
};

``````

Palindrome Partitioning 2
This problem is the most interesting maybe, we need to check it for many times

``````class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));
vector<int> dp(n, n);
for(int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (s[i] == s[j] && (i - j < 2 || isPalindrome[j + 1][i - 1])) {
isPalindrome[j][i] = true;
//case : j == 0
if (isPalindrome[0][i]) dp[i] = 0;
else {
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
}
}
return dp[n - 1];
}
};

``````

Check whether the linked list is palindrome, just reverse the half and check one by one .

``````class Solution {
public:
ListNode* dummy = new ListNode(-1);
ListNode* slow = dummy, *fast = dummy;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
reverse(slow);
else return false;
}
return true;
}

ListNode* start = head->next, *cur = start->next;
while (cur) {
start->next = cur->next;
cur = start->next;
}
return;
}
};
``````

Construct all the possible Palindrome Pairs

We need to recheck this problem

``````
class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> result;
unordered_map<string, int> dict;
for(int i = 0; i < words.size(); i++) {
dict[words[i]] = i;
}
for(int i = 0; i < words.size(); i++) {
for(int j = 0; j <= words[i].length(); j++) {
//suffix string is palindrome, so we can add at the end of the string
if (is_palindrome(words[i], j, words[i].size() - 1)) {
string suffix = words[i].substr(0, j);
reverse(suffix.begin(), suffix.end());
if (dict.find(suffix) != dict.end() && i != dict[suffix]) {
result.push_back({i, dict[suffix]});
}
}
if(j > 0 && is_palindrome(words[i], 0, j - 1)) {
string prefix = words[i].substr(j);
reverse(prefix.begin(), prefix.end());
if (dict.find(prefix) != dict.end() && dict[prefix] != i) {
result.push_back({dict[prefix], i});
}
}
}
}
return result;
}

bool is_palindrome(string& s, int start, int end) {
while (start < end) {
if (s[start++] != s[end--]) {
return false;
}
}
return true;
}
};
``````

Palindrome Permutation 1

``````class Solution {
public:
bool canPermutePalindrome(string s) {
set<char> t;
for (auto a : s) {
if (t.find(a) == t.end()) t.insert(a);
else t.erase(a);
}
return t.empty() || t.size() == 1;
}
};

class Solution {
public:
bool canPermutePalindrome(string s) {
bitset<256> b;
for (auto a : s) {
b.flip(a);
}
return b.count() < 2;
}
};
``````

Palindrome Permutation 2

``````class Solution {
public:
vector<string> generatePalindromes(string s) {
vector<string> res;
unordered_map<char, int> m;
string t = "", mid = "";
for (auto a : s) ++m[a];
for (auto it : m) {
if (it.second & 1) mid += it.first;
t += string(it.second / 2, it.first);
if (mid.size() > 1) return {};
}
permute(t, 0, mid, res);
return res;
}
void permute(string &t, int start, string mid, vector<string> &res) {
if (start >= t.size()) {
res.push_back(t + mid + string(t.rbegin(), t.rend()));
}
for (int i = start; i < t.size(); ++i) {
if (i != start && t[i] == t[start]) continue;
swap(t[i], t[start]);
permute(t, start + 1, mid, res);
swap(t[i], t[start]);
}
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.