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.

class Solution {
public:
int countSubstrings(string s) {
int ans = 0, n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) {
dp[i][i] = 1;
++ans;
}
for (int len = 2; len <= n; ++len) {
for (int i = 0; i < n; ++i) {
int j = i + len - 1;
if (j >= n)break;
if (s[i] == s[j] && (len == 2 || dp[i + 1][j - 1] == 1)) {
dp[i][j] = 1;
++ans;
}
}
}
return ans;
}
};


LeetCode Palindrome Partitioning

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

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;
}
};


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

class Solution2 {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = n - 1; i >= 0; --i) {
dp[i][i] = 1;
for (int j = i + 1; j < n; ++j) {
if (s[i] == s[j])dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
}
}
return dp[0][n - 1];
}
};


class Solution {
private:
int helper(int l, int r, const string &s, vector<vector<int>> &dp) {
if (l > r)return 0;
if (l == r)return 1;
if (dp[l][r] != 0)return dp[l][r];
if (s[l] == s[r])dp[l][r] = helper(l + 1, r - 1, s, dp) + 2;
else dp[l][r] = max(helper(l, r - 1, s, dp), helper(l + 1, r, s, dp));
return dp[l][r];
}
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
return helper(0, n - 1, s, dp);
}
};


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.

class Solution {
public:
int longestPalindrome(string s) {
unordered_map<char, int> hash;
for (int i = 0; i < s.size(); ++i) {
++hash[s[i]];
}
int ans = 0;
int odd = 0;
unordered_map<char, int>::iterator it = hash.begin();
while (it != hash.end()) {
if ((it->second) & 1) {
odd = 1;
ans += it->second - 1;
} else {
ans += it->second;
}
++it;
}
return ans + odd;
}
};


Given a singly linked list, determine if it is a palindrome.
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:
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 true;
}
};


LeetCode Valid Palindrome

LeetCode Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.

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;
}
};


LeetCode Palindrome Partitioning II

LeetCode 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.
For example, given s = "aab",
Return 1 since 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];
}
};


LeetCode Palindrome Number

LeetCode Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.

Some hints:Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.

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;
}
};


LeetCode Longest Palindromic Substring

LeetCode 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, and there exists one unique longest palindromic substring.

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);
}
};


hihoCoder 1032-最长回文子串

hihoCoder 1032-最长回文子串
#1032 : 最长回文子串

3
abababa
aaaabaa
acacdas

7
5
3

1. 首先将字符串S预处理成T。在S的字符之间插入#字符，如下：

For example: S = “abaaba”, T = “#a#b#a#a#b#a#”.

2. 我们将中间结果存储在数组P中：

T = # a # b # a # a # b # a #
P = 0 1 0 3 0 1 6 1 0 3 0 1 0

P[i]表示以T[i]为中心，T中回文串的半径，比如T[3]=b，P[3]=3，表示以b为中心，T中回文串的半径为3，也就是#a#b#a#，半径就是#a#，而P[3]=3也正好是原始串S中以b为中心的回文串的总长度，即回文串aba的长度为3.

3. 为了求数组P，有两种情况需要讨论。假设我们已经求出一部分数组P的值了，如下图所示：
C为目前P中最大值的位置，C为目前T中使得R推进到最右边的回文串的中心位置center（不一定是P的最大值的位置，最大值还需要在最后一步求解），它的半径是9，所以左边（Left）到达L，右边（Right）到达R，下标分别是2和20.
4. 第一种情况是，如果此时i=13，则P[13]等于多少呢？

i的对称点i'下标为9，P[i']=1，它的回文串没有超出以C为中心的回文串，根据对称性，则P[i]=P[i']=1.
5. 第二种情况是，如果i=15，则P[15]等于多少呢？

6. 总结一下就是：

if P[ i' ] ≤ R – i,
then P[ i ] ← P[ i' ]
else P[ i ] ≥ P[ i' ]. (Which we have to expand past the right edge (R) to find P[ i ].

#include&lt;iostream&gt;
#include&lt;string&gt;
using namespace std;
//字符串预处理，插空#，首尾分别^&amp;
string pre_process(string s)
{
string rs;
int s_len=s.size();
if(s_len==0)
return "^&amp;";
rs="^";
for(int i=0;i&lt;s_len;i++)
//rs+="#"+s[i];//const char* 和int/char不能相加，指针越界
rs+="#"+s.substr(i,1);//const char*和string可以相加
return rs+"#&amp;";
}
int get_longest_pal_len(string s)
{
string T=pre_process(s);
int n=T.size();
int *P=new int[T.size()];
P[0]=0;
int C=0,R=0;
for(int i=1;i&lt;n-1;i++) {
int i_mirror=2*C-i;//i的对称位置
P[i]=(R&gt;i)?min(R-i,P[i_mirror]):0;//如果R&gt;i，说明i还在R里面，如果P[i_mirror]&lt;=R-i，则类似图中i=13；如果P[i_mirror]&gt;R-i，则P[i]至少是R-i的，然后从R-i递增测试
while(T[i+1+P[i]]==T[i-1-P[i]])
P[i]++;
if(i+P[i]&gt;R)//更新最大的中心点和右边界
{
C=i;
R=i+P[i];
}
}
int max_len=0;
for(int i=1;i&lt;n-1;i++) {
if(P[i]&gt;max_len)//寻找最大P[i]，P[i]既是T[i]的回文串半径（包含#），也是以S[i]为中心的最长回文串长度。
max_len=P[i];
}
delete[] P;
return max_len;
}
int main()
{
int n;
string s;
cin&gt;&gt;n;
while(n--)
{
cin&gt;&gt;s;
cout&lt;&lt;get_longest_pal_len(s)&lt;&lt;endl;
}
return 0;
}