Palindrome

Wiki

A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward. Allowances may be made for adjustments to capital letters, punctuation, and word dividers. Examples in English include “A man, a plan, a canal, Panama!”, “Amor, Roma”, “race car”, “stack cats”, “step on no pets”, “taco cat”, “put it up”, “Was it a car or a cat I saw?” and “No ‘x’ in Nixon”.

Problems

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.

test

Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
string longestPalindrome(string s) {
int sLen = s.length(), maxLen = 0, maxStart = 0;
int i = 0, l = 0, r = 0, len = 0;
while(i<=sLen-maxLen/2) {
l = r = i;
while(r<sLen-1 && s[r+1]==s[r]) r++;
i = r+1;
while(l>0 && r<sLen-1 && s[r+1]==s[l-1]) l--, r++;
len = r-l+1;
if(maxLen < len) maxLen = len, maxStart = l;
}
return s.substr(maxStart, maxLen);
}
};

Palindrome Pairs

Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:
Given words = [“bat”, “tab”, “cat”]
Return [[0, 1], [1, 0]]
The palindromes are [“battab”, “tabbat”]

Example 2:
Given words = [“abcd”, “dcba”, “lls”, “s”, “sssll”]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are [“dcbaabcd”, “abcddcba”, “slls”, “llssssll”]

test

Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
ass Solution {
private:
bool isPal(string& s, int l, int r) {
while(l<r && s[l]==s[r]) l++, r--;
return l >= r;
}
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> vv;
if(words.size() == 0) return vv;
unordered_map<string, int> word_map;
for(int i = 0; i < words.size(); ++i) word_map[words[i]] = i;
for(int i = 0; i < words.size(); ++i) {
int len = words[i].length(), t;
string cur = words[i], t_str;
reverse(cur.begin(), cur.end());
for(int l = 0; l <= len; ++l) {
if(isPal(cur, 0, l-1)) {
t_str = cur.substr(l);
if(word_map.count(t_str)) {
t = word_map[t_str];
if(t != i) vv.push_back(vector<int>{i, t});
}
}
if(isPal(cur, l, len-1)) {
t_str = cur.substr(0, l);
if(word_map.count(t_str)) {
t = word_map[t_str];
if(len > l) vv.push_back(vector<int>{t, i});
}
}
}
}
return vv;
}
};

Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:
Given “aacecaaa”, return “aaacecaaa”.

Given “abcd”, return “dcbabcd”.

test

Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
string shortestPalindrome(string s)
{
string r_s = s;
reverse(r_s.begin(), r_s.end());
string kmp_s = s+"#"+r_s;
int next[kmp_s.size()]{0};
next[0] = 0;
for(int i = 1; i < kmp_s.length(); ++i) {
int j = next[i-1];
while(j>0 && kmp_s[i]!=kmp_s[j]) j = next[j-1];
next[i] = j+(kmp_s[i]==kmp_s[j]);
}
return r_s.substr(0, r_s.length()-next[kmp_s.size()-1])+s;
}
};

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

test

Solution
  • Using DP to accelerate the backtracking process.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
private:
int sLen;
void search(string& s, int pos, bool** isPal, vector<string>& v, vector<vector<string>>& vv) {
if(pos == sLen) { vv.push_back(v); return ; }
for(int i = pos; i < sLen; ++i) {
if(isPal[pos][i]) {
v.push_back(s.substr(pos, i-pos+1));
search(s, i+1, isPal, v, vv);
v.pop_back();
}
}
}
public:
vector<vector<string>> partition(string s) {
sLen = s.length();
bool **isPal = (bool**)malloc(sizeof(bool*)*sLen);
for(int i = 0; i < sLen; ++i) {
isPal[i] = (bool*)malloc(sizeof(bool)*sLen);
memset(isPal[i], 0, sizeof(bool)*sLen);
}
for(int i = sLen-1; i >= 0; --i)
for(int j = i; j < sLen; ++j)
if(s[j]==s[i] && (j-i<2 || isPal[i+1][j-1]))
isPal[i][j] = true;
vector<string> v;
vector<vector<string>> vv;
search(s, 0, isPal, v, vv);
return vv;
}
};

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.

test

Solution
  • build up the two dimentional matrix while retrieving the result.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int minCut(string s) {
int sLen = s.length();
bool pal[sLen][sLen];
memset(pal, 0, sizeof(bool)*sLen*sLen);
int minCuts[sLen];
for(int i = sLen-1; i >= 0; --i) {
minCuts[i] = INT_MAX;
for(int j = i; j < sLen; ++j) {
if(s[i]==s[j] && (j-i<2 || pal[i+1][j-1])) {
pal[i][j] = 1;
if(j == sLen-1) minCuts[i] = 0;
else minCuts[i] = min(minCuts[i], minCuts[j+1]+1);
}
}
}
return minCuts[0];
}
};

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.

test

Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
bool isPalindrome(string s) {
int l = 0, r = s.length()-1;
while(l < r) {
while(!isalnum(s[l])) l++;
while(!isalnum(s[r])) r--;
if(tolower(s[l]) != tolower(s[r])) break;
l++, r--;
}
return l >= r;
}
};

Palindrome Number

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

test

Solution
  • Just reverse the whole number.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution {
    public:
    bool isPalindrome(int x) {
    if(x < 0) return false;
    long a = 0, t = x;
    while(t) {
    a = 10*a + t%10;
    t /= 10;
    }
    return a == x;
    }
    };
  • Just reverse half of the number, but we have to exclude some exceptions before.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution {
    public:
    bool isPalindrome(int x) {
    if(x<0 || (x>0 && x%10==0)) return false;
    int a = 0;
    while(a < x) {
    a = 10*a + x%10;
    x /= 10;
    }
    return a>x? a/10==x : a==x;
    }
    };

Palindrome Permutation II

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:
Given s = “aabb”, return [“abba”, “baab”].
Given s = “abc”, return [].

Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
vector<string> generatePalindromes(string s) {
vector<string> palindromes;
int counts[256]{0};
for (char c : s) counts[c]++;
int odd = 0; char mid; string half;
for(int i = 0; i < 256; ++i){
if (counts[i] & 1) {
odd++, mid = i;
if (odd > 1) return palindromes;
}
half += string(counts[i]/2, i);
}
cout<<"here"<<endl;
palindromes = permutations(half);
for (string& p : palindromes) {
string t(p);
reverse(t.begin(), t.end());
if(odd) t = mid + t;
p += t;
}
return palindromes;
}
private:
vector<string> permutations(string& s) {
vector<string> perms;
string t(s);
do {
perms.push_back(s);
next_permutation(s.begin(), s.end());
} while (s != t);
return perms;
}
};

C basics

haracter classification functions
They check whether the character passed as parameter belongs to a certain category:

  • isalnum Check if character is alphanumeric (function)
  • isalpha Check if character is alphabetic (function)
  • isblank Check if character is blank (function)
  • iscntrl Check if character is a control character (function)
  • isdigit Check if character is decimal digit (function)
  • isgraph Check if character has graphical representation (function)
  • islower Check if character is lowercase letter (function)
  • isprint Check if character is printable (function)
  • ispunct Check if character is a punctuation character (function)
  • isspace Check if character is a white-space (function)
  • isupper Check if character is uppercase letter (function)
  • isxdigit Check if character is hexadecimal digit (function)

Character conversion functions

  • tolower Convert uppercase letter to lowercase (function)
  • toupper Convert lowercase letter to uppercase (function)

Always welcome new ideas and practical tricks, just leave them in the comments!