Valid Palindrome

• Lintcode : 415 / Leetcode : 125
• Level : Easy

Problem

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

Example
Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama"
Example 2:

Input: "race a car"
Output: false
Explanation: "raceacar"
Challenge
O(n) time without extra memory.

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

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n)
space: O(1)

Answer

class Solution {
public:
    bool isPalindrome(string &s) {
        int l = 0, r = s.size() - 1;
        while (l < r) {
            while (l < r && !isalpha(s[l]) && !isdigit(s[l])) l++;
            while (l < r && !isalpha(s[r]) && !isdigit(s[r])) r--;
            if (l < r && tolower(s[l]) != tolower(s[r])) {
                return false;
            }
            l++, r--;
        }
        return true;
    }
};

tags: string

​