Today I continue the Leetcode grind. Rather than continuing with the Leetcode75 problem set, I pivoted to using the Grind75 site. I like the format of this and it makes it clear what to do each week. We'll see how using this instead will go.
Approach
The problem description is very explicit about what to do to solve this one.
It mentions that after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, checking for palindrome is possible. So that is exactly what I will do.
There are no restrcitions on space complexity so I will start by creating a string newS to hold my cleaned string.
Then, for each character in the input string s, I will check if it is an alphanumeric character using the built-in C++ function isalnum(). If the character is alphanumeric, I make it lowercase.
Now that I have a clean string newS, I can move on to determining if it is a palindrome.
To do this, I create an index called left and one called right, each initialized to the beginning and end of the string. Next, I want to loop half way through the string (no sense in going from beginning to end to) so I set my while condition to while(left < right).
Inside the loop, I check if character at position left is not equal to character at position right. If an instance of this is found, return false. Lastly, inside the loop I decrement right and increment left.
Lastly, if no faults were found when checking for palindrome, I return true.
Fun one!
Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Code
class Solution {
public:
bool isPalindrome(string s) {
string newS = "";
for(char c : s){
if(isalnum(c)){
newS += tolower(c);
}
}
int left = 0, right = newS.length() - 1;
while(left < right){
if(newS[left] != newS[right]){
return false;
}
left++;
right--;
}
return true;
}
};