Two Pointers

Palindrome

Valid Palindrome

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

"A man, a plan, a canal: Panama" -> True
"race a car" -> False

1
2
3
4
5
6
7
8
9
10
11
12
bool isPalindrome(string s) {
int left = 0, right = s.length() -1;
while (left < right)
{
if (!isalnum(s[left])) left++;
else if (!isalnum(s[right])) right--;
else if (tolower(s[left]) != tolower(s[right])) return false;
else { left++; right--; }
}

return true;
}

Util methods: isalnum(char), tolower(char)

Valid Palindrome Allow One Deletion

1
2
3
4
5
6
7
8
9
10
11
bool validPalindrome(string s) {
for (int i = 0, j = s.size() - 1; i < j; i++, j--)
if (s[i] != s[j]) return helper(s, i + 1, j) || helper(s, i, j - 1);
return true;
}

bool helper(const string& s, int l, int r) {
for (int i = l, j = r; i < j; i++, j--)
if (s[i] != s[j]) return false;
return true;
}

Think about Valid Panlindrome allow at most K deletion.

Palindrome Pairs [hard]

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.

Palindrome Number

1
2
3
4
5
6
7
8
9
10
11
12
13
bool isPalindrome(int x) {
if (x < 0) return false; // not negative number
if (x != 0 && x%10 == 0) return false; // not end with 0

// 12321 -> x=12, rev=123
// 1221 -> x=12, rev=12
int rev = 0;
while (x > rev) {
rev = rev*10 + x%10;
x = x / 10;
}
return (x==rev) || (x==rev/10);
}

Similar problem: reverse integer number

1
2
3
4
5
6
7
8
9
10
11
12
13
int reverse(int x) {
int sign = x > 0 ? 1 : -1;
long int r = 0;
x = abs(x);

while (x) {
r = r * 10 + x % 10;
x /= 10;
}
r = sign * r;

return (r > INT_MAX || r < INT_MIN) ? 0 : r;
}

Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s.