# LeetCode Pseudo-Palindromic Paths in a Binary Tree

5418. Pseudo-Palindromic Paths in a Binary Tree

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Example 1:

Input: root = [2,3,1,3,1,null,1]
Output: 2
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).


Example 2:

Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).


Example 3:

Input: root = 
Output: 1


Constraints:

• The given binary tree will have between 1 and 10^5 nodes.
• Node values are digits from 1 to 9.

class Solution {
private:
void DFS(TreeNode* root, vector<int> &hash, int &ans) {
if (root == NULL)return;
++hash[root->val];

if (root->left == NULL && root->right == NULL) {
int odd = 0;
for (int i = 1; i <= 9; ++i) {
if (hash[i] % 2 == 1) {
++odd;
if (odd > 1) {
break;
}
}
}
if (odd <= 1) {
++ans;
}
--hash[root->val];
return;
}

DFS(root->left, hash, ans);
DFS(root->right, hash, ans);
--hash[root->val];
}
public:
int pseudoPalindromicPaths(TreeNode* root) {
vector<int> hash(10, 0);
int ans = 0;
DFS(root, hash, ans);
return ans;
}
};


# LeetCode Palindromic Substrings

LeetCode Palindromic Substrings Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters. Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:
1. The input string length won’t exceed 1000.

# LeetCode Palindrome Partitioning

131. 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.

Example:

Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]

DP求s[i,…,j]是否为回文串的过程是这样的，如果s[i]==s[j]，且dp[i+1][j-1]也是回文串，则dp[i][j]也是回文串。所以我们需要先求到长度比较短的s[i+1,j-1]是否为回文串，然后再求长度更长的是否为回文串。所以在helper函数的外层循环是子串的长度。

class Solution {
private:
void helper(const string& s, vector<vector<int> >& dp)
{
int n = s.size();
for (int i = 0; i < n; ++i)
dp[i][i] = 1; // 单个字符自身就是回文串
for (int len = 2; len <= n; ++len) {
for (int i = 0; i + len – 1 < n; ++i) {
if (s[i] == s[i + len – 1] && ((i + 1 <= i + len – 2 && dp[i + 1][i + len – 2] == 1) || i + 1 > i + len – 2)) {
dp[i][i + len – 1] = 1;
}
}
}
}
void dfs(const string& s, vector<vector<int> >& dp, vector<vector<string> >& ans, vector<string>& cand, int idx)
{
if (idx == s.size()) {
ans.push_back(cand);
return;
}
for (int i = idx; i < s.size(); ++i) {
if (dp[idx][i] == 1) {
cand.push_back(s.substr(idx, i – idx + 1));
dfs(s, dp, ans, cand, i + 1);
cand.pop_back();
}
}
}
public:
vector<vector<string> > partition(string s)
{
int n = s.size();
vector<vector<int> > dp(n, vector<int>(n, 0));
helper(s, dp);
vector<vector<string> > ans;
vector<string> cand;
dfs(s, dp, ans, cand, 0);
return ans;
}
};

class Solution {
public:
bool IsPal(const string &s, int l, int r) {
if (l > r)return false;
if (l == r)return true;
while (l < r) {
if (s[l] != s[r])break;
++l;
--r;
}
return l >= r;
}
void DFS(vector<vector<string>> &ans, vector<string> &cur, string &s, int idx) {
int n = s.size();
if (idx >= n) {
ans.push_back(cur);
return;
}
for (int i = idx; i < n; ++i) {
if (IsPal(s, idx, i)) {
cur.push_back(s.substr(idx, i - idx + 1));
DFS(ans, cur, s, i + 1);
cur.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> ans;
vector<string> cur;
DFS(ans, cur, s, 0);
return ans;
}
};

# LeetCode Longest Palindromic Subsequence

LeetCode Longest Palindromic Subsequence Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000. Example 1: Input:

"bbbab"

Output:
4

One possible longest palindromic subsequence is “bbbb”. Example 2: Input:
"cbbd"

Output:
2

One possible longest palindromic subsequence is “bb”.

# LeetCode Longest Palindrome

LeetCode Longest Palindrome Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters. This is case sensitive, for example "Aa" is not considered a palindrome here. Note: Assume the length of given string will not exceed 1,010. Example:

Input:
"abccccdd"
Output:
7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Could you do it in O(n) time and O(1) space?

1. 1->2->3->4->5->4->3->2->1
2. 1->2->3->4->4->3->2->1

class Solution {
public:
{
return true;
while (faster->next != NULL && faster->next->next != NULL) {
faster = faster->next->next;
slower = slower->next;
} //bool odd = faster->next == NULL ? true : false; // 链表长度是否为奇数
ListNode *head2 = slower, *prior = slower->next, *tail;
while (prior != NULL) { // 逆序后半段链表
tail = prior->next;
prior = tail;
}
return false;
}
return true;
}
};

class Solution {
public:
// 快慢指针
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
// 逆序后半段
ListNode *dummy = new ListNode(0);
ListNode *par = slow, *child = slow->next;
while (par != NULL) {
child = par->next;
par->next = dummy->next;
dummy->next = par;
par = child;
}
// 判断是否相等
fast = dummy->next;
while (fast != NULL) {
if (slow->val != fast->val)return false;
slow = slow->next;
fast = fast->next;
}
return true;
}
};

# LeetCode Valid Palindrome

125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true


Example 2:

Input: "race a car"
Output: false

bool isAlphaNum(char c) { return (c >= ‘A’&& c <= ‘Z’) || (c >= ‘a’&& c <= ‘z’) || (c >= ‘0’&& c <= ‘9’); }
char upper2lower(char c)
{
if (c >= ‘A’&& c <= ‘Z’)
return c + 32;
return c;
}
class Solution {
public:
bool isPalindrome(string s)
{
int i = 0, j = s.size() – 1;
while (i < s.size() && j >= 0) {
while (!isAlphaNum(s[i]) && i < s.size())
i++;
if (i >= s.size())
break;
char c1 = upper2lower(s[i]);
while (!isAlphaNum(s[j]) && j >= 0)
j–;
if (j < 0)
break;
char c2 = upper2lower(s[j]);
if (c1 != c2)
return false;
i++;
j–;
}
return true;
}
};

bool isAlphaNum(char c) { return (c >= ‘A’&& c <= ‘Z’) || (c >= ‘a’&& c <= ‘z’) || (c >= ‘0’&& c <= ‘9’); }
char upper2lower(char c)
{
if (c >= ‘A’&& c <= ‘Z’)
return c + 32;
return c;
}
class Solution {
public:
bool isPalindrome(string s)
{
int i = 0, j = s.size() – 1;
while (i <= j) {
while (!isAlphaNum(s[i]) && i <= j)
i++;
if (i > j)
break;
char c1 = upper2lower(s[i]);
while (!isAlphaNum(s[j]) && i <= j)
j–;
if (i > j)
break;
char c2 = upper2lower(s[j]);
if (c1 != c2)
return false;
i++;
j–;
}
return true;
}
};

class Solution {
public:
bool IsValid(char c) {
return (c >= '0'&&c <= '9') || (c >= 'a'&&c <= 'z');
}
bool isPalindrome(string s) {
int n = s.size();
if (n == 0 || n == 1)return true;
int i = 0, j = n - 1;
while (i < j) {
s[i] = tolower(s[i]);
s[j] = tolower(s[j]);

if (!IsValid(s[i]))++i;
else if (!IsValid(s[j]))--j;
else {
if (s[i] != s[j])break;
else {
++i;
--j;
}
}
}
return i >= j;
}
};

# LeetCode Palindrome Partitioning II

132. Palindrome Partitioning II

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

Return the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

class Solution {
public:
int minCut(string s)
{
int n = s.size();
vector<vector<bool> > dp(n, vector<bool>(n, false));
for (int i = 0; i < n; i++)
dp[i][i] = true;
vector<int> cut(n, 0); // # of cut for s[0,j]
for (int j = 0; j < n; j++) {
cut[j] = j; // set maximum # of cut
for (int i = 0; i <= j; i++) {
if (s[i] == s[j] && (j – i <= 1 || dp[i + 1][j – 1])) {
dp[i][j] = true;
if (i > 0) // if need to cut, add 1 to the previous cut[i-1]
cut[j] = min(cut[j], cut[i – 1] + 1);
else // if [0…j] is palindrome, no need to cut cut[j] = 0;
}
}
}
return cut[n – 1];
}
};

.......aba...
|<-X->| ^
|<---Y-->|


class Solution {
public:
int minCut(string s)
{
int n = s.size();
vector<int> cuts(n + 1, 0); // cuts[i] 表示前i个字符切成回文子串，最少的刀数
for (int i = 0; i <= n; ++i)
cuts[i] = i – 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; i – j >= 0 && i + j < n && s[i – j] == s[i + j]; ++j) // 最后一个是奇数长回文子串
cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i – j] + 1);
for (int j = 1; i – j + 1 >= 0 && i + j < n && s[i – j + 1] == s[i + j]; ++j) // 最后一个是偶数长回文子串
cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i – j + 1] + 1);
}
return cuts[n];
}
};

class Solution {
public:
void preprocess(const string &s, vector<vector<int>> &dp) {
int n = s.size();
for (int i = 0; i < n; ++i)dp[i][i] = 1;
for (int len = 2; len <= n; ++len) {
for (int i = 0; i < n; ++i) {
int j = i + len - 1;
if (j < n && s[i] == s[j] && (len == 2 || dp[i + 1][j - 1] == 1)) {
dp[i][j] = 1;
}
}
}
}
int minCut(string s) {
int n = s.size();
if (n == 0 || n == 1)return 0;
vector<vector<int>> dp(n, vector<int>(n, 0));
preprocess(s, dp);
vector<int> dp2(n, 0);
for (int j = 1; j < n; ++j) {
dp2[j] = dp2[j - 1] + 1;
for (int i = j - 1; i >= 0; --i) {
if (dp[i][j] == 1) {
int pre_cut = i > 0 ? dp2[i - 1] + 1 : 0;
dp2[j] = min(dp2[j], pre_cut);
}
}
}
return dp2[n - 1];
}
};

# LeetCode Palindrome Number

9. Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true


Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.


Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.


Coud you solve it without converting the integer to a string?

class Solution {
public:
bool isPalindrome(int x)
{
if (x < 10)
return x >= 0;
if (x % 10 == 0)
return false;
int y = 0;
while (x > y) {
y = y * 10 + x % 10;
if (x == y) //76567
return true;
x /= 10;
if (x == y) //765567
return true;
}
return false;
}
};

class Solution {
public:
bool isPalindrome(int x) {
if(x < 0) return false;
if(x == 0) return true;
if(x % 10 == 0) return false;

vector<int> digits;
while(x != 0) {
digits.push_back(x % 10);
x /= 10;
}
int l = 0, r = digits.size() - 1;
while(l < r) {
if(digits[l] != digits[r]) return false;
++l;
--r;
}
return true;
}
};

# LeetCode Longest Palindromic Substring

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.


Example 2:

Input: "cbbd"
Output: "bb"

class Solution {
public:
string preProcess(string s)
{
int n = s.size();
if (n == 0)
return "^#";
string ret = "^";
for (int i = 0; i < n; i++)
ret += "#" + s.substr(i, 1);
return ret + "#$"; } string longestPalindrome(string s) { string t = preProcess(s); vector<int> p(t.size(), 0); int c = 0, r = 0, n = t.size(); for (int i = 1; i < n - 1; i++) { int i_mirror = 2 * c - i; p[i] = (r > i) ? min(p[i_mirror], r - i) : 0; while (t[i + p[i] + 1] == t[i - p[i] - 1]) p[i]++; if (i + p[i] > r) { c = i; r = i + p[i]; } } int maxLen = 0, centerIndex = 0; for (int i = 1; i < n - 1; i++) { if (p[i] > maxLen) { maxLen = p[i]; centerIndex = i; } } return s.substr((centerIndex - 1 - maxLen) / 2, maxLen); } }; 本代码提交AC，用时12MS，击败了73%的CPP用户，看来效率不错，估计中心扩展法$O(n^2)\$也能过。

class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n == 0)return "";
vector<vector<int>> dp(n, vector<int>(n, 0));
int ans = 1, u = 0, v = 0;
for (int len = 0; len < n; ++len) {
for (int i = 0; i < n; ++i) {
int j = i + len;
if (j >= n)break;

if (len == 0)dp[i][j] = 1;
else if (len == 1) {
if (s[i] == s[j]) {
dp[i][j] = 1;
if (2 > ans) {
ans = 2;
u = i;
v = j;
}
}
}
else {
if (dp[i + 1][j - 1] == 1 && s[i] == s[j]) {
dp[i][j] = 1;
if (j - i + 1 > ans) {
ans = j - i + 1;
u = i;
v = j;
}
}
}
}
}
return s.substr(u, v - u + 1);
}
};

class Solution {
public:
int expand(string &s, int l, int r) {
int n = s.size();
while (l >= 0 && r < n&&s[l] == s[r]) {
--l;
++r;
}
return r - l - 1;
}
string longestPalindrome(string s) {
if (s.size() == 0)return "";
string ans = "";
for (int i = 0; i < s.size(); ++i) {
int len1= expand(s, i, i);
int len2= expand(s, i, i + 1);
if (len1 > len2&&len1 > ans.size()) {
ans = s.substr(i - len1 / 2, len1);
}
if (len2 > len1&&len2 > ans.size()) {
ans = s.substr(i - len2 / 2 + 1, len2);
}
}
return ans;
}
};