Cinte's Leetcode Record
0%

125. Valid Palindrome

Posted on Edited on In Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

125. Valid Palindrome

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:
    bool isPalindrome(string s) {
        auto lo = s.begin();
        auto hi = s.end() - 1;
        while(lo < hi)
        {
            if(*lo <= 'Z' && *lo >= 'A')
                *lo += 32;
            if(*hi <= 'Z' && *hi >= 'A')
                *hi += 32;
            if(!isDigitalOrAlphabet(*lo))
                ++lo;
            else if(!isDigitalOrAlphabet(*hi))
                --hi;
            else
            {
                if(*lo != *hi)
                    return false;
                ++lo;
                --hi;
            }
            
        }
        return true;
    }
private:
    bool isDigitalOrAlphabet(char& ch)
    {
        if((ch >= 'a' && ch < 'z') || (ch >= '0' && ch <= '9'))
            return true;
        else
            return false;
    }
};

T(n): O(n)

S(n): O(1)

review
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while(left < right)
        {
            while(left < right && !isValid(s[left]))
                ++left;
            while(left < right && !isValid(s[right]))
                --right;
            if(left >= right)
                break;
            if(tolower(s[left++]) != tolower(s[right--]))
                return false;
        }
        return true;
    }
private:
    inline bool isValid(char ch)
    {
        return (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9') || (ch >= 'A' && ch <= 'Z');
    }
};