Strings

They’re great.

Valid Palindromes - Easy

This version is only concerned with alphanumeric characters (letters and numbers) so you need to strip and trim of anything else. There’s a few ways to do this, I used Recursion cuz I’m a smartass. Idea:

1. Base case: when length of string is 1 or less → return True.
2. Check if first and last characters are the NOT the same, then return False.
3. Else, do the recursive call on the substring, work your way in from the outside, pinching both ends one character at a time. Example:

class Solution {
    /**
    Prepare the string by removing all non alphanumeric characters.
     */
    public String prepareString(String input){
        return input.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
    }
 
    public boolean checkPalindrome(String input) {
        // String tidyStr = prepareString(s);
        if(input.length() <= 1){
            return true;
        }
        else{
            // System.out.println(tidyStr);
            if(input.charAt(0) != input.charAt(input.length() - 1)){
                return false;
            }
            else {
                return checkPalindrome(input.substring(1, input.length() - 1));
            }
        }
    }
 
	// Did this because only wanted to preprocess once...
    public boolean isPalindrome(String s){
        String tidyStr = prepareString(s);
        return checkPalindrome(tidyStr);
    }
}

This recursive solution is VERY slow.

Whereas this one is $O(log(n)$ :

class Solution:
    def isPalindrome(self, s: str) -> bool:
        if len(s) <= 1:
            return True
 
        formatted_input = re.sub(r'[^a-zA-Z0-9]', '', s).lower()
        length = len(formatted_input)
 
        index = 0
        while index < len(formatted_input) // 2:
            if formatted_input[index] != formatted_input[length - index - 1]:
                return False
            index += 1
        return True