~/leetcode $ 125. Valid Palindrome

Moved onto the two pointer section of neetcode150…

For this problem, we want to know if the string is the same when read both forwards and backwards. Thinking about brute force, we can have two pointers (one from the start and one from the end) and check if the current character at each pointer is the same. We can continue moving these pointers towards each other and if at any time the characters are different, the words are not a valid palindrome.

One thing to realise is that there is no need to wait until both of the pointers are at the end of the string. We can stop when the two pointers pass each other as we know that once we reach that point, all subsequent checks are going to be true.

One thing we need to keep in mind is that we first need to convert all uppercase letters into lowercase letters and remove all non-alphanumeric characters as per the requirements. Unfortunately, I don’t know how to do that in cpp so more learning yay:

• convert to lowercase using std::tolower(char) (in the <cctype> header) which I think ignores non alpha characters
• check for alphanumeric using std::isalnum(char) (in the <cctype> header)

class Solution {
public:
    bool isPalindrome(string s) {
        string newStr {};
        for (char ch: s) {
            if (isalnum(ch)) {
                newStr += tolower(ch);
            }
        }

        int left = 0;
        int right = newStr.size() - 1;
        while (left < right) {
            if (newStr[left++] != newStr[right--]) {
                return false;
            }
        }

        return true;
    }
}

Time Complexity: O(n)

Space Complexity: O(n)

Time Taken: 2m 27s