No need for inner while loops if we check the following:
- if s[l].isalpha() and s[r].isalpha(): # inside, return False if chars (lower cased) don’t equal, or advance both pointers
- elif not s[l].isalpha(): # advance l past non-alpha
- elif not s[r].isalpha(): # advance r past non-alpha
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.
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;
}
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
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
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.
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
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]
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;
}
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
}
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;
}
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.
and the magic solution:
return sorted(s) == sorted(s, reverse=True)
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
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.
Much simpler, but has worse time complexity: NlogN
vs O(N)
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]