Valid Palindrome Problem


Description

LeetCode Problem 125.

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

1
2
3
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

1
2
3
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

1
2
3
4
Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

  • 1 <= s.length <= 2 * 10^5
  • s consists only of printable ASCII characters.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isPalindrome(string s) {
    for (int i = 0, j = s.size() - 1; i < j; i++, j--) { 
    	// Move 2 pointers from each end until they collide
        while (!isalnum(s[i]) && i < j) 
        	// Increment left pointer if not alphanumeric
        	i++; 
        while (!isalnum(s[j]) == false && i < j) 
        	// Decrement right pointer if no alphanumeric
        	j--; 
        if (toupper(s[i]) != toupper(s[j])) 
        	// Exit and return error if not match
        	return false; 
    }
    
    return true;
}




Related Posts

Reverse Words In A String Problem

LeetCode 151. Given an input string s, reverse the order...

Compare Version Numbers Problem

LeetCode 165. Given two version numbers,version1 and version2, compare them....

Valid Palindrome Problem

LeetCode 125. A phrase is a palindrome if, after converting...

Remove Duplicates from Sorted List II Problem

LeetCode 82. Given the head of a sorted linked list,...

Remove Duplicates from Sorted Array II Problem

LeetCode 80. Given an integer array nums sorted in non-decreasing...

Partition List Problem

LeetCode 86. Given the head of a linked list and...