My AC solution.


  • 0
    D

    let's make two pointers L, R: L it is index of first valid char and R is index of last valid char. Then we should check whether s[L] and s[R] are equal.
    The space complexity of this algorithm is O(1) and O(n) time, where n is length of the string.

     class Solution {
        public:
            bool isPalindrome(string s) {
                int l = 0, r = s.size() - 1;
                bool ok = true;
                while (l < r){
                    while (l < s.size() && !isLetter(s[l]) && !isNumber(s[l])) l++;
                    while (r >= 0 && !isLetter(s[r]) && !isNumber(s[r])) r--;
                    if (l == s.size() || r < 0) break;
                    if (isLetter(s[l]) && isLetter(s[r])){
                        char a = tolower(s[l]), b = tolower(s[r]);
                        if (a != b) ok = false;
                    }else
                    if (s[l] != s[r]) ok = false;
                    l++; r--;
                }
                return ok;
            }
            bool isLetter(char x){
                return ((x >= 'A' && x <= 'Z') || (x >= 'a' && x <= 'z'));
            }
            bool isNumber(char x){
                return (x >= '0' && x <= '9');
            }
            
        };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.