Valid Palindrome - Two Pointers / Opposite Direction

Problems
1

https://algo.monster/problems/valid_palindrome

2

No need for inner while loops if we check the following:

  1. if s[l].isalpha() and s[r].isalpha(): # inside, return False if chars (lower cased) don’t equal, or advance both pointers
  2. elif not s[l].isalpha(): # advance l past non-alpha
  3. elif not s[r].isalpha(): # advance r past non-alpha
3

Thanks for explaining the space and time complexity for removing the non-alphanumeric characters first. I thought the time complexity would’ve been higher, but its the space that increases.

4

You could use a regex to remove non alpha numeric characters and then process the string.

function isPalindrome(s) {
const str = s.replace(/[^a-z0-9]/gi, ‘’).toLowerCase();

let l = 0;
let r = str.length - 1;

while(l<=r){
    if(str.charAt(l) !== str.charAt(r))
        return false;
    
    l++;
    r--;
}

return true;

}

5

Python has default isalpha() to test whether a string only has alphabetic characters, we can pre-processing s to a valid string with only alpha and lower case:

def is_palindrome(s: str) → bool:
pro_s = [char for char in s.lower() if char.isalpha()]
left, right = 0, len(pro_s) - 1
while left < right:
if pro_s[left] != pro_s[right]:
return False
left += 1
right -= 1
return True

6

Solution w/ generators

def is_palindrome(s: str) → bool:
def gen(s, reverse=False):
if reverse:
s = s[::-1]

    for c in s:
        if not c.isalnum():
            continue
        yield c.lower()

for left, right in zip(gen(s), gen(s, True)):
    if None in [left, right] or left != right:
        return False
return True
7

I don’t know regex well enough to be able to use it for filtering during an interview. I’ll just create a map of all the valid characters (in lowercase) and check if the lowercase version of each char in the original string is in the map which should still be in constant time and therefore linear for the entire filter.

8

def is_palindrome(s: str) → bool:
# WRITE YOUR BRILLIANT CODE HERE

#
# Defeculties I faced or missed:
#    1- I missed the fist while line 8 and 
#       I put after the two while in line 10 and 12. This a bad bug 
#
#    2- I miss to check for s[..].isalnum()
#    3- I forgot to use s[..].lower, didnt read the note 1 & 2 below ;-(
#


l, r = 0, len(s)-1

while (l < r):

    while (l < r) and not s[l].isalnum():
        l += 1
    while (l < r) and not s[r].isalnum():
        r -= 1
        
    if s[r].lower() != s[l].lower():
        return False
    else:
        r -= 1
        l += 1
        
return True
9

Anything wrong with the below?

import re
class Solution:
def isPalindrome(self, s: str) → bool:
s = s.lower()
s = re.sub(r"[^a-z0-9]", “”, s)
return s == s[::-1]

10 
public static boolean isPalindrome(String s) {
        s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        int left = 0;
        int right = s.length() - 1;
        
        while (left < right) {
            if (s.charAt(left) != s.charAt(right))
                return false;
            left++;
            right--;
        }
        return true;
    }
11

An alternative JS solution:

function isPalindrome(s) {
    const str = s.toLowerCase().replace(/\W+/g, '')

    for (let i = 0, len = str.length; i < len; i++) {
        if (str.charAt(i) !== str.charAt(len - i - 1)) return false
    }

    return true
}
12 
    public static boolean isPalindrome(String s) {
        String fixedString = ""; 

        for (char c : s.toLowerCase().toCharArray()){
            if(Character.isDigit(c) || Character.isLetter(c)){
                fixedString += c;
            }
        }

        int l = 0; 
        int r = fixedString.length() - 1;

        while(l <= r){
            if(fixedString.charAt(l) != fixedString.charAt(r)){
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
13

I think the first implementation in Java also has space complexity of O(n). According to String 's javadoc, toCharArray creates “a newly allocated character array whose length is the length of this string and whose contents are initialized to contain the character sequence represented by this string”. Therefore, calling toCharArray has an O(n) space complexity.

14

and the magic solution:

return sorted(s) == sorted(s, reverse=True)
15

def is_palindrome(s: str) → bool:
s = s.lower()
left = 0
right = len(s) - 1

while left < right:
    if not s[left].isalnum():
        left += 1
    elif not s[right].isalnum():
        right -= 1
    elif s[left] == s[right]:
        left += 1
        right -= 1
    else:
        return False

return True
16

I think there should be a test case to check for consecutive non-alphanumeric characters. I was able to come up with a solution that only used if instead of a while loop and thought I did it correctly.

17

Much simpler, but has worse time complexity: NlogN vs O(N)

18

Here is a 2 line Python solution that is linear runtime complexity

def is_palindrome(s: str) -> bool:
    s = "".join([c for c in s if c.isalnum()])
    return s.replace(" ", "").lower() == s.replace(" ", "").lower()[::-1]