Neetcode Solution
class Solution:
def isPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
while l < r and not self.alphanum(s[l]):
l += 1
while l < r and not self.alphanum(s[r]):
r -= 1
if s[l].lower() != s[r].lower():
return False
l += 1
r -= 1
return True
# Could write own alpha-numeric function
def alphanum(self, c):
return (
ord("A") <= ord(c) <= ord("Z")
or ord("a") <= ord(c) <= ord("z")
or ord("0") <= ord(c) <= ord("9")
)Note
alphanum during coding interviews to avoid having to look up the ascii table. Also, he did it in place, without extra space.
My Solution without the Ugly reversed() Shenanigans
def discard_bad_apples(s):
good_apples = []
for c in s:
ordinal_of_c = ord(c)
if ordinal_of_c >= 97 and ordinal_of_c <= 122:
good_apples.append(c)
elif ordinal_of_c >= 48 and ordinal_of_c <= 57:
good_apples.append(chr(ordinal_of_c))
elif ordinal_of_c >= 65 and ordinal_of_c <= 90:
good_apples.append(chr(ordinal_of_c + 32))
return good_apples
class Solution:
def isPalindrome(self, s: str) -> bool:
good_apples = discard_bad_apples(s)
n = len(good_apples)
if n <= 1:
return True
if n % 2 == 0:
original_first_part = good_apples[0:n//2]
original_second_part = good_apples[n//2:n]
else:
original_first_part = good_apples[0:n//2]
original_second_part = good_apples[n//2 + 1:n]
reversed_second_part = original_second_part[::-1]
return original_first_part == reversed_second_partMy Solution without Converting back into a String
def discard_bad_apples(s):
good_apples = []
for c in s:
ordinal_of_c = ord(c)
if ordinal_of_c >= 97 and ordinal_of_c <= 122:
good_apples.append(c)
elif ordinal_of_c >= 48 and ordinal_of_c <= 57:
good_apples.append(chr(ordinal_of_c))
elif ordinal_of_c >= 65 and ordinal_of_c <= 90:
good_apples.append(chr(ordinal_of_c + 32))
return good_apples
class Solution:
def isPalindrome(self, s: str) -> bool:
good_apples = discard_bad_apples(s)
n = len(good_apples)
if n <= 1:
return True
if n % 2 == 0:
original_first_part = good_apples[0:n//2]
original_second_part = good_apples[n//2:n]
else:
original_first_part = good_apples[0:n//2]
original_second_part = good_apples[n//2 + 1:n]
reversed_second_part = list(reversed(list(original_second_part)))
return original_first_part == reversed_second_part
Warning
Do not trust the runtimes too much. It oscilates between 96% and 61%
My Faster Solution but Would Take way Too long in a Coding Interview
def discard_bad_apples(s):
good_apples = []
for c in s:
ordinal_of_c = ord(c)
if ordinal_of_c >= 97 and ordinal_of_c <= 122:
good_apples.append(c)
elif ordinal_of_c >= 48 and ordinal_of_c <= 57:
good_apples.append(chr(ordinal_of_c))
elif ordinal_of_c >= 65 and ordinal_of_c <= 90:
good_apples.append(chr(ordinal_of_c + 32))
return ''.join(good_apples)
class Solution:
def isPalindrome(self, s: str) -> bool:
good_apples = discard_bad_apples(s)
n = len(good_apples)
if n <= 1:
return True
if n % 2 == 0:
original_first_part = good_apples[0:n//2]
original_second_part = good_apples[n//2:n]
else:
original_first_part = good_apples[0:n//2]
original_second_part = good_apples[n//2 + 1:n]
reversed_second_part = ''.join(reversed(list(original_second_part)))
return original_first_part == reversed_second_part
My Clean Solution
def discard_bad_apples(s):
good_apples = []
for c in s:
ordinal_of_c = ord(c)
if ordinal_of_c >= 97 and ordinal_of_c <= 122:
good_apples.append(c)
elif ordinal_of_c >= 48 and ordinal_of_c <= 57:
good_apples.append(chr(ordinal_of_c))
elif ordinal_of_c >= 65 and ordinal_of_c <= 90:
good_apples.append(chr(ordinal_of_c + 32))
return good_apples
class Solution:
def isPalindrome(self, s: str) -> bool:
good_apples = discard_bad_apples(s)
n = len(good_apples)
if n <= 1:
return True
i = 0
j = n - 1
while i < j:
print(good_apples[i], good_apples[j])
if good_apples[i] != good_apples[j]:
return False
i += 1
j -= 1
return True
Info
Passing in list(s) to discard_bad_apples actually gives a worse runtime of 56ms! (though not by much, so it probably doesn’t make much difference)
To speed up, you could discard bad apples in place, and thereby avoid having to go to an entire subroutine first, which is instead of just .
Older Dirty Solution
class Solution:
def isPalindrome(self, s: str) -> bool:
ascii = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t",
"u", "v", "w", "x", "y", "z", '0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
s = s.lower()
copyOfS = []
for c in s:
if c in ascii:
copyOfS.append(c)
s = ''.join(copyOfS)
n = len(s)
if n == 1:
return True
if n == 2:
return s[0] == s[1]
if n % 2 == 0:
mid = n // 2
left_part = s[0:mid]
right_part = s[mid:n]
return left_part == right_part[::-1]
i = 0
j = n - 1
while i != j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True