I'm currently prepping to interview with Google in a couple months. Just wanted to let you know you've been an extremely helpful resource in getting ready for this! Thank you so much and hoping all is well :)
Lol same, i started practising DSA again since last week and couldn't solve a single problem this one i was able to solve with the same technique i know its an easy problem still feels good
The reason why the first solution is faster than the second one is that the method isalnum() is written in C behind the scenes while the solution you achieved is written in pure Python. C is a much more performant language than python, so thats why. Interestingly, a large part of Python methods are written in C.
ive tested your solution and ya it works thanks...but im not sure if just using the characters like that would be ok with the interviewer since just checking "a"
That works in JavaScript as well! I just found that using the function returns ascii value such as String.codePointAt() for example in JS, would be a option considering readability. ...If you ever wanted the code for code interview to be easier to read, though🥴
Heres an optimization ive noticed....you can avoid having to write while l < r in the checking parts again by changing it to an if statement and using continue.. so it would be something like: if not alphanum(s[l]) : l+=1 continue same for right pointer if not alphanum(s[r]) : r-=1 continue
@@harperbye its been 4 months, but each should be doing a check of the condition. So in general I don't think one is faster than the other. However I try to avoid while loops if I can, because they can cause an infinite loop if theres a bug in the code :)
Could someone elaborate on why he includes "l < r" and "r > l" in the internal while loops? My assumption is that the outermost while loop already accounts for that piece of logic (while l < r:...)
The nested while loops is a bit hard to read. We could easily do with if else statements: while l < r: if not self.alphaNum(s[l]): l += 1 elif not self.alphaNum(s[r]): r -= 1 elif s[l].lower() == s[r].lower(): l += 1 r -= 1 else: return False return True
The first solution is actually O(n^2) time where n is number of alphanumeric characters. This is because python strings are immutable. "Appending" a character creates a new string each iteration. It's better to build the new string with a list, and then using join later.
Instead of using a helper function, I made a set consisting of all alpha numeric characters and checked using that. I got 80MS runtime and 14.4MB memory usage!
@@LightningRod maybe, it feels like hard-coding cuz u have to enter every letter by yourself. if they ask it other way around you can't write all non-alphanumeric values into set
Took me minutes to a variant of the first solution (using comprehension list), whereas other medium challenges in LeetCode take me hours and I often need to check the solution to get it, the difficulty level is all over the place on LeetCode, I don't get how they rank it.
I think, instead of having same check inside while loop, would be better if we skip the iteration, something like this if(!alphaNum(s[i])){ i+=1; continue; } if(!alphaNum(s[j])){ j-=1; continue; }
Hey man I noticed that the actual reason you got a slow problem is that you use the ".lower()" function several times per iteration, if you just convert the string into lowercase from the beginning the approach becomes a lot faster.
Can anyone explain why do we have to put "while l < r" again inside of the first while loop? the loop bound is already assigned in the first while loop..
I'd imagine it is just an extra check to make sure that specific left pointer is still less than the right pointer. Same for the right pointer making sure it is moving left and not crossing each other. It is his way of making sure that the two do not cross as they are ignoring white spaces and non-alphanumeric numbers. Might be off the mark a bit but that is the general gist.
Completely wrong, the outer loop is make sure the left and right pointer don't cross because you're incrementing the left and decrementing the right pointer. If they cross you'd end up comparing stuff again and also running into issues where the corresponding char in the palindrome is being compared to a random one. Anyways, the inner two loops are to ensure the current left/right chars the pointers are pointing to are in fact alphanumeric, they have nothing to do with the pointers crossing. Since you don't have the luxury of creating a new string, you want to work with what you have, so you're just going to ignore any 'bad' (non-alphanumeric strings) until both are alphanumeric. Then, you do the comparison. Why give feedback when you're wrong.@@messiworldcupwinner
You can use regex: class Solution: def isPalindrome(self, s: str) -> bool: s = re.sub('[^0-9a-zA-Z]+', '', s) s = s.lower().strip() if s == s[::-1]: return True else: return False
Because both the pointers are only covering half the list before meeting in the middle and they're only visiting each element once. It's n^2 if you're doing something like incrementing the first pointer only after the second pointer has traversed all the elements in the list.
If you have "abcd" ( len 4 ) and you have to visit 4 times for each char (always!) for any reason , a :4 times , b:4 times -> ... and so on .... 4x4= 16 time complexity O(n^2)
Initially, you told that "your solution" has time TC=O(n) but when you coded it up, I found it to be O(n^2). I will explain this how- Input: s = 'a+_+_+_+_+_+_+aaa' TC of your code- while l
While working in Javascript I changed the code for using regex instead of ascii for validating alphanumeric values also instead of using while inside of while loop I changed it to if statement const isValidPalindrome = (str) => { let left = 0; let right = str.length - 1; while (left < right) { if (!/^[a-zA-Z0-9]+$/.test(str[left])) { left += 1; continue; } if (!/^[a-zA-Z0-9]+$/.test(str[right])) { right -= 1; continue; } if (str[left].toLowerCase() !== str[right].toLowerCase()) { return false; } left += 1; right -= 1; } return true; };
The following solution achieved a runtime of 58 ms with optimizations made to the while loops in order to enhance its efficiency:
def isPlanidrome(self , s): start = 0 end = len(s) - 1 while start < end: if self.isalpha(s[start]) and self.isalpha(s[end]): if s[start].lower() == s[end].lower(): start += 1 end -= 1 else: return False else: if not self.isalpha(s[start]): start += 1 if not self.isalpha(s[end]): end -= 1 return True def isalpha(self , c): return (ord('A')
It seems some class error happens if alphaNum() function is defined within the Solution class. This updated code works in python3: class Solution: def isPalindrome(self, s: str) -> bool: def isAlphaNumeric(c): return (ord('A')
I saw this solution on leetcode by Tushar_thoriya class Solution: def isPalindrome(self, s: str) -> bool: newStr = "" for c in s: if c.isalnum(): newStr += c.lower() return newStr == newStr[::-1]
Can someon please explain why we do l , r=0, len(s)-1 what is len(s)-1 assigned to why are commas separating these values? Also why do we have l,r=l+1 , r -1 shouldn't it just be r-1 as we're decrementing what do these lines mean and what do they do?
its a shorthand way to assign values basically this is equivalent to l = l+1 r= r-1 that takes 2 lines to put it on one line you can comma separate. its a python trick
can I just write like this def isalNum(c) ? When I use def isalNum(self, c), while not isalNum(s[l]) and l < r or while not self.isalNum(s[l]) and l < r: will report error?
Looks like the second solution fails for the following testcases: s = "a." and s=".;". The reason is that the inner while loops overshoot end up pointing to non-alpha-numeric characters. I found using if statements and only incrementing l or r (and not both) inside the outer while loops helps avoid this issue.
Hi@@antoniocipriano1070 Here you go def isPalindrome(self, s: str) -> bool: l, r = 0, len(s) - 1 while l < r: if not self.isAlphaNum(s[l]): l += 1 elif not self.isAlphaNum(s[r]): r -= 1 elif s[l].lower() == s[r].lower(): l += 1 r -= 1 else: return False return True
class Solution: def isPalindrome(self, s: str) -> bool: filtered_string = ''.join(e.lower() for e in s if e.isalnum()) for i in range(len(filtered_string)): if filtered_string[i] != filtered_string[-1-i]: return False return True
while l < r: while l< r and not s[l].isalnum(): l += 1 while r > l and not s[r].isalnum(): r -= 1 if l < r and s[l].lower() != s[r].lower(): return False l = l +1 r = r - 1 return True
Can someone explain to me in more detail why at 13:10 why you need another set of L < R inside the already existing L < R while loop so that it doesn't go out of bound
Reason being that the outer loop is make sure the left and right pointer don't cross because you're incrementing the left and decrementing the right pointer. If they cross you'd end up comparing stuff again and also running into issues where the corresponding char in the palindrome is being compared to a random one. Anyways, the inner two loops are to ensure the current left/right chars the pointers are pointing to are in fact alphanumeric, they have nothing to do with the pointers crossing. Since you don't have the luxury of creating a new string, you want to work with what you have, so you're just going to ignore any 'bad' (non-alphanumeric strings) until both are alphanumeric. Then, you do the comparison, and update the pointers afterwards. Ask chatGPT to do a trace.
Two other ways: def isPalindrome(self, s: str) -> bool: s = s.lower() res = [] for c in s: if c.isalnum(): res.append(c) s = ''.join(res) return True if s == ''.join(reversed(s)) else False And: def isPalindrome(self, s: str) -> bool: s = s.lower() l, r = 0 , len(s)-1 while l
Hi just found your channel. Algorithms give me this PTSD vibes even though I have not really tried them. So where do I start from on the channel. I want to know this!!
Just wanted to share my solution. It did pretty well and It's quite simple: def isPalindrome(self, s: str) -> bool: new_s = "" for i in range(len(s)): if 96 < ord(s[i]) < 123 or 47 < ord(s[i]) < 58: new_s += s[i] continue if 64 < ord(s[i]) < 91: new_s += chr(ord(s[i]) + 32) continue return new_s == new_s[::-1]
I wonder if this string would be a valid test case 'a man ap ...!. panama' according to the rules, it should be a palindrome, but the second solution would return false.
what is the reason for writing a custom alpha numeric function? how do you what you are writing is more optimized than boiler plate isalnum() function?
My solution was using regex. cleaned = re.sub(r'[^A-Za-z0-9]', '', s).lower() If cleaned == cleaned[::-1] and not cleaned.isdigit() > return True Which results in a much shorter code, but a bit of an overhead in time complexity due to regex and modifying the string.
hey there.. I developed a sol in java . leetcode says 79% efficient in space: here the code: s = s.replaceAll("[^a-zA-Z0-9]", ""); String temp = s.toLowerCase().trim(); int fp = 0; int lp = temp.length()-1; while (fp
Why wouldn't you just use a for loop here since you know you're looping temp.length/2 times? I think the point of the while loop is to independently move the pointers.
Likely because alnum() is very python specific, but every language for the most part has a lower() of some sorts. I couldn't imagine an interviewer asking to implement your own lowercase function unless that was its own question
A single inner while loop only traverses half of the string. Even though there are two inner loops, they visit all elements in the string exactly once. Accessing an element in string is O(1). Accessing all element in string is still constant time O(1)
10 question in: I am still unsure whether I should implement my own functions or use the already implemented ones. I am thinking about performance too much even tho I should only think at the lvl of big o complexity lvl. I should have been a c developer with this autisticity 💀🃏
Suppose string = "Tanuj" then len(string) = 5, which is the number of elements in the string. However the index looks like this: string[0] = T string[1] = a string[2] = n string[3] = u string[4] = j string[len(string)] would be string[5], it would be out of range. Therefore the last character is always len(string) - 1.
Python has built-in utility to check alphanumeric: str.isalnum() That leetcode benchmark is not reliable, you can submit repeatedly and get varying results.
Hi I used this: import re def isPalindrome(s): s = re.sub("[^a-z0-9]", "", s.lower()) print(s) return True if s[::-1] == s else False def isPalindrome1(s): s = "".join([c for c in s.lower() if 96 < ord(c) < 123 or 47 < ord(c) < 58 ]) print(s) return True if s[::-1] == s else False
I'm currently prepping to interview with Google in a couple months. Just wanted to let you know you've been an extremely helpful resource in getting ready for this! Thank you so much and hoping all is well :)
Good luck Stephen, you're gonna do great!
Good luck bro
howd it go!!??
Did you get the role?
@@nero9985 never interviewed, the recruiters kept me in limbo so long until I took a job elsewhere
It's so damn satisfying having done a solution and seeing that Neetcode uses the absolute same method.
Lol same, i started practising DSA again since last week and couldn't solve a single problem this one i was able to solve with the same technique i know its an easy problem still feels good
The reason why the first solution is faster than the second one is that the method isalnum() is written in C behind the scenes while the solution you achieved is written in pure Python. C is a much more performant language than python, so thats why. Interestingly, a large part of Python methods are written in C.
That explains why the inbuilt methods are almost always faster than my custom ones.
interesting!
Actually, we can write function for checking alphanumeric characters like this and it will work
def isalnum(c: str) -> bool:
return (("a"
ive tested your solution and ya it works thanks...but im not sure if just using the characters like that would be ok with the interviewer since just checking "a"
@@turtlenekk4354 I think that either solution is ok. If you can show several ways of doing the same thing it would be even better
Did not know this about python, thank you!
just tried it - good to know! thx
That works in JavaScript as well! I just found that using the function returns ascii value such as String.codePointAt() for example in JS, would be a option considering readability.
...If you ever wanted the code for code interview to be easier to read, though🥴
Heres an optimization ive noticed....you can avoid having to write while l < r in the checking parts again by changing it to an if statement and using continue.. so it would be something like:
if not alphanum(s[l]) :
l+=1
continue
same for right pointer
if not alphanum(s[r]) :
r-=1
continue
This is a good idea. Reduces the code complexity!
i thought while loops are more faster than if statements, why should we avoid while loops? (im a beginner in python so im not really sure)
@@harperbye its been 4 months, but each should be doing a check of the condition. So in general I don't think one is faster than the other. However I try to avoid while loops if I can, because they can cause an infinite loop if theres a bug in the code :)
i think this won't work for this: s= "AB{[BA"
Yes!!! Thank you for continuing with the LC 75 series!! We all really appreciate it.
I'd let out a big sigh if the interviewer asked for another approach after I show him the first solution
Abaha fr
I picked up blind-75 aswell! Keep up the grind as always 💪
Could someone elaborate on why he includes "l < r" and "r > l" in the internal while loops? My assumption is that the outermost while loop already accounts for that piece of logic (while l < r:...)
Yeah, but you change the L and R values within the internal while loops, so you need to check again.
If the string only has symbols you are cooked
The nested while loops is a bit hard to read. We could easily do with if else statements:
while l < r:
if not self.alphaNum(s[l]):
l += 1
elif not self.alphaNum(s[r]):
r -= 1
elif s[l].lower() == s[r].lower():
l += 1
r -= 1
else:
return False
return True
After LC 75 is done, can you do the SeanPrashad 170 questions? If you have both playlists, that would be HUGE
+1 to this ... can we do this?
@@showmethemoney824 +1
i ended up using this is_alnum function instead of the one used in the solution. it made more sense to me than using the
The first solution is actually O(n^2) time where n is number of alphanumeric characters.
This is because python strings are immutable. "Appending" a character creates a new string each iteration.
It's better to build the new string with a list, and then using join later.
Instead of using a helper function, I made a set consisting of all alpha numeric characters and checked using that. I got 80MS runtime and 14.4MB memory usage!
How did you get past the "0P" case? It keeps failing for me there with set.
@@TethiusMC use .isalnum instead of .isalpha
this is actually bad practice but i guess LC baits you into writing bad code sometimes
@@Yougottacryforthis Can you elaborate?
@@LightningRod maybe, it feels like hard-coding cuz u have to enter every letter by yourself. if they ask it other way around you can't write all non-alphanumeric values into set
Took me minutes to a variant of the first solution (using comprehension list), whereas other medium challenges in LeetCode take me hours and I often need to check the solution to get it, the difficulty level is all over the place on LeetCode, I don't get how they rank it.
I think, instead of having same check inside while loop, would be better if we skip the iteration, something like this
if(!alphaNum(s[i])){
i+=1;
continue;
}
if(!alphaNum(s[j])){
j-=1;
continue;
}
yeah, was thinking the same
@@mikelexx2542 it is not O(n^2) it is still O(n)
Ok, I'm going to be positive and say that, this is a great question. What it thought me stayed and made me a better programmer.
Hey man I noticed that the actual reason you got a slow problem is that you use the ".lower()" function several times per iteration, if you just convert the string into lowercase from the beginning the approach becomes a lot faster.
But it will create a new string right?
@@negaaa5080 I think it's better to sacrifice a little bit of space complexity, for a better improvement in time complexity, but that's just me.
Same here!
The whole basis for the second solution was a space-time trade off for O(1) additional space from the start though.
Can anyone explain why do we have to put "while l < r" again inside of the first while loop? the loop bound is already assigned in the first while loop..
I'd imagine it is just an extra check to make sure that specific left pointer is still less than the right pointer. Same for the right pointer making sure it is moving left and not crossing each other. It is his way of making sure that the two do not cross as they are ignoring white spaces and non-alphanumeric numbers. Might be off the mark a bit but that is the general gist.
Completely wrong, the outer loop is make sure the left and right pointer don't cross because you're incrementing the left and decrementing the right pointer. If they cross you'd end up comparing stuff again and also running into issues where the corresponding char in the palindrome is being compared to a random one. Anyways, the inner two loops are to ensure the current left/right chars the pointers are pointing to are in fact alphanumeric, they have nothing to do with the pointers crossing. Since you don't have the luxury of creating a new string, you want to work with what you have, so you're just going to ignore any 'bad' (non-alphanumeric strings) until both are alphanumeric. Then, you do the comparison. Why give feedback when you're wrong.@@messiworldcupwinner
I used regex for both extra space solution and no extra space solution:
def isPalindrome(self, s: str) -> bool:
pattern = re.compile(r"[0-9a-zA-Z]+")
char_list = pattern.findall(s)
new_str = "".join(char_list).lower()
left_pointer, right_pointer = 0, len(new_str)-1
while left_pointer < right_pointer:
if new_str[left_pointer] != new_str[right_pointer]:
return False
left_pointer += 1
right_pointer -= 1
return True
def isPalindrome2(self, s: str) -> bool:
left_pointer, right_pointer = 0, len(s)-1
while left_pointer < right_pointer:
while left_pointer < right_pointer and not re.match(r"[0-9a-zA-Z]+", s[left_pointer]):
left_pointer += 1
while left_pointer < right_pointer and not re.match(r"[0-9a-zA-Z]+", s[right_pointer]):
right_pointer -= 1
if s[left_pointer].lower() != s[right_pointer].lower():
return False
left_pointer += 1
right_pointer -= 1
return True
I'm probably going to name my first child after you if I get the job.
lol
You're gonna name your child "Neet"?
@@anantprakashsingh8777sounds cool though!
class Solution:
def isPalindrome(self, s: str) -> bool:
s = list(map(lambda x: x.lower(),filter(lambda x: x.isalnum(),s)))
return s==s[::-1]
Less number of lines doesn't equals more efficient
this solution is probably O(n!) time lmao
You can use regex:
class Solution:
def isPalindrome(self, s: str) -> bool:
s = re.sub('[^0-9a-zA-Z]+', '', s)
s = s.lower().strip()
if s == s[::-1]:
return True
else:
return False
you can just return s == s[::-1]:
no need for if else return true false
@@ohhellnooooo8233 oh nice, thank you!!
I was wondering why O(N) and not O(N^2) because of nested while loop.
Because both the pointers are only covering half the list before meeting in the middle and they're only visiting each element once. It's n^2 if you're doing something like incrementing the first pointer only after the second pointer has traversed all the elements in the list.
its not n^2 because we are visiting each element only once
If you have "abcd" ( len 4 ) and you have to visit 4 times for each char (always!) for any reason ,
a :4 times , b:4 times -> ... and so on .... 4x4= 16
time complexity O(n^2)
why not convert the input string to lower from start? is it because that would cause more memory?
thank you neetcode
Initially, you told that "your solution" has time TC=O(n) but when you coded it up, I found it to be O(n^2). I will explain this how-
Input: s = 'a+_+_+_+_+_+_+aaa'
TC of your code-
while l
Great video
youre the goat man, do you have a linkedin?
When you find Neetcode's solution for your search on youtube..Happiness >>>>>
While working in Javascript I changed the code for using regex instead of ascii for validating alphanumeric values also instead of using while inside of while loop I changed it to if statement
const isValidPalindrome = (str) => {
let left = 0;
let right = str.length - 1;
while (left < right) {
if (!/^[a-zA-Z0-9]+$/.test(str[left])) {
left += 1;
continue;
}
if (!/^[a-zA-Z0-9]+$/.test(str[right])) {
right -= 1;
continue;
}
if (str[left].toLowerCase() !== str[right].toLowerCase()) {
return false;
}
left += 1;
right -= 1;
}
return true;
};
Excellent explanation
The following solution achieved a runtime of 58 ms with optimizations made to the while loops in order to enhance its efficiency:
def isPlanidrome(self , s):
start = 0
end = len(s) - 1
while start < end:
if self.isalpha(s[start]) and self.isalpha(s[end]):
if s[start].lower() == s[end].lower():
start += 1
end -= 1
else:
return False
else:
if not self.isalpha(s[start]):
start += 1
if not self.isalpha(s[end]):
end -= 1
return True
def isalpha(self , c):
return (ord('A')
It seems some class error happens if alphaNum() function is defined within the Solution class. This updated code works in python3:
class Solution:
def isPalindrome(self, s: str) -> bool:
def isAlphaNumeric(c):
return (ord('A')
Thank you so much!
Superb
I saw this solution on leetcode by Tushar_thoriya
class Solution:
def isPalindrome(self, s: str) -> bool:
newStr = ""
for c in s:
if c.isalnum():
newStr += c.lower()
return newStr == newStr[::-1]
Can someon please explain why we do l , r=0, len(s)-1 what is len(s)-1 assigned to why are commas separating these values?
Also why do we have l,r=l+1 , r -1 shouldn't it just be r-1 as we're decrementing what do these lines mean and what do they do?
its a shorthand way to assign values
basically this is equivalent to
l = l+1
r= r-1
that takes 2 lines
to put it on one line you can comma separate. its a python trick
really good one
This problem teaches me a lot of useful things
whats next for the channel once you finish the 75 list?
interviewer could also ask to not use character.lower() inbuilt function
can I just write like this def isalNum(c) ? When I use def isalNum(self, c), while not isalNum(s[l]) and l < r or while not self.isalNum(s[l]) and l < r: will report error?
string concatenation is not really happening in python as string is immutable. Better to store all in list and then "".join(lst)
Isn't two while loops O(N^2)? Why are we using that when we can do this in O(N)?
Hi, thanks so much for sharing this. QQ around l==r case incase of odd number of characters, don't you think thats required?
Looks like the second solution fails for the following testcases: s = "a." and s=".;". The reason is that the inner while loops overshoot end up pointing to non-alpha-numeric characters. I found using if statements and only incrementing l or r (and not both) inside the outer while loops helps avoid this issue.
can you show ur solution for this. I am also running into the same failure for these testcases.
Hi@@antoniocipriano1070 Here you go
def isPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
if not self.isAlphaNum(s[l]):
l += 1
elif not self.isAlphaNum(s[r]):
r -= 1
elif s[l].lower() == s[r].lower():
l += 1
r -= 1
else:
return False
return True
in the question howd u know you can ignore the punctuation ?
class Solution:
def isPalindrome(self, s: str) -> bool:
filtered_string = ''.join(e.lower() for e in s if e.isalnum())
for i in range(len(filtered_string)):
if filtered_string[i] != filtered_string[-1-i]:
return False
return True
Beautiful solution
class Solution:
def isPalindrome(self, s: str) -> bool:
l, r= 0, len(s)-1
while l < r:
while l< r and not s[l].isalnum():
l += 1
while r > l and not s[r].isalnum():
r -= 1
if l < r and s[l].lower() != s[r].lower():
return False
l = l +1
r = r - 1
return True
I am facing this problem : TypeError: ord() expected string of length 1, but int found
Can someone explain to me in more detail why at 13:10 why you need another set of L < R inside the already existing L < R while loop so that it doesn't go out of bound
If l increments inside that while loop, then l will equal r, but we need that extra check so we don't possibly increment l again in that case.
Reason being that the outer loop is make sure the left and right pointer don't cross because you're incrementing the left and decrementing the right pointer. If they cross you'd end up comparing stuff again and also running into issues where the corresponding char in the palindrome is being compared to a random one. Anyways, the inner two loops are to ensure the current left/right chars the pointers are pointing to are in fact alphanumeric, they have nothing to do with the pointers crossing. Since you don't have the luxury of creating a new string, you want to work with what you have, so you're just going to ignore any 'bad' (non-alphanumeric strings) until both are alphanumeric. Then, you do the comparison, and update the pointers afterwards. Ask chatGPT to do a trace.
Two other ways:
def isPalindrome(self, s: str) -> bool:
s = s.lower()
res = []
for c in s:
if c.isalnum():
res.append(c)
s = ''.join(res)
return True if s == ''.join(reversed(s)) else False
And:
def isPalindrome(self, s: str) -> bool:
s = s.lower()
l, r = 0 , len(s)-1
while l
Hi just found your channel. Algorithms give me this PTSD vibes even though I have not really tried them. So where do I start from on the channel. I want to know this!!
so much info in such a short video
Just wanted to share my solution. It did pretty well and It's quite simple:
def isPalindrome(self, s: str) -> bool:
new_s = ""
for i in range(len(s)):
if 96 < ord(s[i]) < 123 or 47 < ord(s[i]) < 58:
new_s += s[i]
continue
if 64 < ord(s[i]) < 91:
new_s += chr(ord(s[i]) + 32)
continue
return new_s == new_s[::-1]
Hey Neet theres a slight error with the alphanum while statement for the right pointer in the python code on your site, just change it up later ig !
I wonder if this string would be a valid test case 'a man ap ...!. panama' according to the rules, it should be a palindrome, but the second solution would return false.
can we add equality in the while statement: l
nice solution thank you
what is the reason for writing a custom alpha numeric function? how do you what you are writing is more optimized than boiler plate isalnum() function?
just in case an interviewer doesn't what you to use built in functions like that
Thank you!
My solution was using regex.
cleaned = re.sub(r'[^A-Za-z0-9]', '', s).lower()
If cleaned == cleaned[::-1] and not cleaned.isdigit() > return True
Which results in a much shorter code, but a bit of an overhead in time complexity due to regex and modifying the string.
I am getting type error for alphaNum function
It saying
'
Why not just use the method, .alnum(), instead of making a helper function? What implications does that have for time and space complexity
If s= "AB{[BA"
Code works but still it won't shift the r to 2nd position
Great!
At first, I thought the second approach would be faster because it only needs to iterate half of the string. Can someone explain why it not?
I was wrong about it, the 2nd approach still iterates through the entire string
For one thing, it's also using a nested while loop. The second method is actually quadratic in time complexity. On paper it's worse than the first.
I used two pointers but with Regex.. is it bad?
In this solution won't "a!@#$" return true and "ab!@#$" return false due to the nature of the inc/dec while loops? 🤔
"ab!@#$" will just be ab which is not a palindrome so it should return false. what am I missing?
hey there..
I developed a sol in java .
leetcode says 79% efficient in space:
here the code:
s = s.replaceAll("[^a-zA-Z0-9]", "");
String temp = s.toLowerCase().trim();
int fp = 0;
int lp = temp.length()-1;
while (fp
Why wouldn't you just use a for loop here since you know you're looping temp.length/2 times? I think the point of the while loop is to independently move the pointers.
@@JeffRagusa right...later I found that way also....👍😀 But totally forgot to update here
Why does this question have so many downvotes on leetcode?
thanks! but why is it ok to use builtin .lower() but not builtin .alnum()?
Likely because alnum() is very python specific, but every language for the most part has a lower() of some sorts. I couldn't imagine an interviewer asking to implement your own lowercase function unless that was its own question
we have loop inside loop how the time complexity could be o(n)???
A single inner while loop only traverses half of the string. Even though there are two inner loops, they visit all elements in the string exactly once. Accessing an element in string is O(1). Accessing all element in string is still constant time O(1)
having 2 while loop in this case == O(n²) time?
10 question in: I am still unsure whether I should implement my own functions or use the already implemented ones. I am thinking about performance too much even tho I should only think at the lvl of big o complexity lvl.
I should have been a c developer with this autisticity 💀🃏
thanks !!
Thanks u
13:58
Could someone explain me why r = len(s)-1.. why -1 is used?
Suppose string = "Tanuj"
then len(string) = 5, which is the number of elements in the string.
However the index looks like this:
string[0] = T
string[1] = a
string[2] = n
string[3] = u
string[4] = j
string[len(string)] would be string[5], it would be out of range.
Therefore the last character is always len(string) - 1.
@@eduardofernandes9998 Thank you so much
understood
def isPalindrome(self, s: str) -> bool:
s = [c.lower() for c in s if c.isalnum()]
return s[:] == s[::-1]
Why is this problem disliked so much?
we can use .isalnum() for checking if the number is alpha numeric, and thanks for the series blind75 compilation.
Python has built-in utility to check alphanumeric: str.isalnum()
That leetcode benchmark is not reliable, you can submit repeatedly and get varying results.
const s = "A man, a plan, a canal: Panama";
function isCharValid(char){
if(char === " "){
return false;
}
if(!isNaN(char)){
return true;
}
const lowerCaseChar = char.toLowerCase();
const upperCaseChar = char.toUpperCase();
if(lowerCaseChar.charCodeAt(0) - upperCaseChar.charCodeAt(0) === 32){
return true;
}
return false;
}
function sanitizedString(str){
let newSanitizedString = "";
for( let i = 0; i < str.length; i++){
if(isCharValid(str.charAt(i))){
newSanitizedString += str.charAt(i).toLowerCase();
}
}
return newSanitizedString;
}
function isSanitizedStrPalindrome(str){
let start = 0;
let end = str.length - 1;
while(start < end){
if(str.charAt(start) !== str.charAt(end)){
return false;
}
++start;
--end;
}
return true;
}
function solve(){
const newSanitizedString = sanitizedString(s);
return isSanitizedStrPalindrome(newSanitizedString);
}
console.log(solve())
Hi I used this:
import re
def isPalindrome(s):
s = re.sub("[^a-z0-9]", "", s.lower())
print(s)
return True if s[::-1] == s else False
def isPalindrome1(s):
s = "".join([c for c in s.lower() if 96 < ord(c) < 123 or 47 < ord(c) < 58 ])
print(s)
return True if s[::-1] == s else False
I don't know why it always reports an error - NameError: name 'alphaNum' is not defined, but I'm clearly doing exactly what you guys are doing.🥲
Superb