Leetcode - Valid Palindrome

Leetcode : Valid Palindrome

Description

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

Example 1

Input

"A man, a plan, a canal: Panama"

Output

true

Example 2

Input

"race a car"

Output

false

Approach

Different approaches can be taken to determine whether the given input string s is a palindrome or not (i.e - convert string to Ascii Number to remove space and non-alphanumerica values, make additional string and replicate the original input and then return the boolean value)

Solutions (C++)

Solution 1

class Solution {
public:
    bool isPalindrome(string s) {
        string newString = "";
        string testString = "";
        
        for (int i = 0; i < s.length(); i++)
        {
            char lowerCase = tolower(s[i]);
            
            if (!((lowerCase >= 'a' && lowerCase <= 'z') || (lowerCase >= '0' && lowerCase <= '9')))
                continue;
            else
                newString += lowerCase;
        }
        
        for (int i = newString.length() - 1; i >= 0; i--)
        {
            testString += newString[i];
        }
        
        return testString == newString;
        
    }
};

Result

Runtime : 16ms
Memory Usage : 7.8MB
Runtime Beats 45.02% of C++ Submission

Solution 2

class Solution {
public:
	bool isPalindrome(string s) {
		int start = 0;
		int end = s.size() - 1;

		while (start < end) {
			char sc = tolower(s[start]);
			char ec = tolower(s[end]);


			if (!((sc >= 'a' && sc <= 'z') || (sc >= '0' && sc <= '9'))) {
				start++;
			}
			else if (!((ec >= 'a' && ec <= 'z') || (ec >= '0' && ec <= '9'))) {
				end--;
			}
			else {
				if (sc != ec)
					return false;
				start++;
				end--;
			}
		}

		return true;
	}
};

Result

Runtime : 12ms
Memory Usage : 7.2MB
Runtime Beats 86.90% of C++ Submission