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
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 :)
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.
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 :)
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🥴
@@danielniels22 Every single time you append a string you create a new one under the hood and it requires O(n) time to recreate the new string with the next character. So, when you recreateString(1) + recreateString(2) + recreateString(3) ... recreateString(n) AKA for char in string: newString += char, you end up with 1 + 2 + 3 ... n operations. This is synonymous with the sum of natural numbers which is roughly = to n^2. If you're still not sure, then ask chatGPT to explain it and copy paste what i've said along with the code he provided!
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:...)
Bit late to the party here, but the internal while loop could step out of bounds if the a string has only non alphanumeric characters. Python throws an IndexError when this occurs.
I'm really glad that you use a different solution here that is actually O(n) rather than the advanced algorithms course. I see in the advanced algorithms course that you clean the string using appending method to a new string. In fact, if this is a paid course it is IMPERATIVE that you clarify that the method used there is polynomial time to clean the string. Because under the hood you are doing 1 + 2 + 3 ... N operations since it instantiates a new string each time you append a char. That's the impression I'm under, someone correct me if i'm wrong, and if that's not clarified in the course then it's really going to be a shame when someone fails an interview because of it.
@@zackthebest629 Yeah this is what I just did, 4ms, 19.09mb. I feel like its a better (definitely cleaner) solution but I'm not sure if NeetCode isn't using it because Regex is built in maybe?
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
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 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.
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.
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 dodnt understand how stupid it is interviewers asking not using isalnum() in interviews its good to have knowledge on language specific helpful function.
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; }
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!!
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
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?
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?
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
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)
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]
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
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')
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; };
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]
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
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')
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
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
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)
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.
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
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
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.
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.
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 💀🃏
Noob here, why can't you just import regex, lower case everything, filter out non a-z0-9 characters and then reverse a copy of a list. import re class Solution: def isPalindrome(self, s: str) -> bool: s = s.lower() s = re.sub(r'[^a-z0-9]', '', s) srev = s[::-1] if s == srev: return True else: return False
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.
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
Python has built-in utility to check alphanumeric: str.isalnum() That leetcode benchmark is not reliable, you can submit repeatedly and get varying results.
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
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
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!
Yes!!! Thank you for continuing with the LC 75 series!! We all really appreciate it.
I picked up blind-75 aswell! Keep up the grind as always 💪
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"
@@prasid33 It works. L = R on the last iteration of the while loop, so the loop breaks and True is returned.
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🥴
I'd let out a big sigh if the interviewer asked for another approach after I show him the first solution
Abaha fr
I mean, it's fair bc the cleaning method is bounded by the sum of natural numbers leading to a polynomial runtime.
@@AustinCSwhat do you mean by this?
@@danielniels22 Every single time you append a string you create a new one under the hood and it requires O(n) time to recreate the new string with the next character. So, when you recreateString(1) + recreateString(2) + recreateString(3) ... recreateString(n) AKA for char in string: newString += char, you end up with 1 + 2 + 3 ... n operations. This is synonymous with the sum of natural numbers which is roughly = to n^2. If you're still not sure, then ask chatGPT to explain it and copy paste what i've said along with the code he provided!
7:03 Yeah, but ord() and chr() are also built-in functions like isallnum().
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
Bit late to the party here, but the internal while loop could step out of bounds if the a string has only non alphanumeric characters. Python throws an IndexError when this occurs.
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'm really glad that you use a different solution here that is actually O(n) rather than the advanced algorithms course. I see in the advanced algorithms course that you clean the string using appending method to a new string. In fact, if this is a paid course it is IMPERATIVE that you clarify that the method used there is polynomial time to clean the string. Because under the hood you are doing 1 + 2 + 3 ... N operations since it instantiates a new string each time you append a char. That's the impression I'm under, someone correct me if i'm wrong, and if that's not clarified in the course then it's really going to be a shame when someone fails an interview because of it.
Helpful video. One can also perform a regex check to make sure the character values are in the alphanumeric range
yep thats what i tried :
class Solution:
def isPalindrome(self, s: str) -> bool:
no_spaces = re.sub(r'[^a-zA-Z0-9]','',s).lower()
return no_spaces[::-1] == no_spaces
@@zackthebest629 Yeah this is what I just did, 4ms, 19.09mb. I feel like its a better (definitely cleaner) solution but I'm not sure if NeetCode isn't using it because Regex is built in maybe?
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.
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
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
thank you neetcode
I solved this already , but coming here I see instead of remembering ASCII code it is fine to use the function and this is was a saviour.
youre the goat man, do you have a linkedin?
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.
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!
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 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.
Great video
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.
When you find Neetcode's solution for your search on youtube..Happiness >>>>>
Excellent explanation
really good one
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 dodnt understand how stupid it is interviewers asking not using isalnum() in interviews its good to have knowledge on language specific helpful function.
whats next for the channel once you finish the 75 list?
Beautiful solution
why not convert the input string to lower from start? is it because that would cause more memory?
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)
so much info in such a short video
This problem teaches me a lot of useful things
nice solution thank you
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!!
Thank you!
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
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
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?
Superb
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
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 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)
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]
Isn't two while loops O(N^2)? Why are we using that when we can do this in O(N)?
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
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!
13:58
I am getting type error for alphaNum function
It saying
'
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;
};
in the question howd u know you can ignore the punctuation ?
Great!
thanks !!
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]
can we add equality in the while statement: l
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
Hi, thanks so much for sharing this. QQ around l==r case incase of odd number of characters, don't you think thats required?
thanks :)
technically the first solution is faster because you wrote it faster
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
string concatenation is not really happening in python as string is immutable. Better to store all in list and then "".join(lst)
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')
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 used two pointers but with Regex.. is it bad?
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
Thanks u
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)
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 not just use the method, .alnum(), instead of making a helper function? What implications does that have for time and space complexity
interviewer could also ask to not use character.lower() inbuilt function
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?
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
understood
Why does this question have so many downvotes on leetcode?
I am facing this problem : TypeError: ord() expected string of length 1, but int found
you're passing an int as an argument to ord(). Stop doing that.
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.
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
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
If s= "AB{[BA"
Code works but still it won't shift the r to 2nd position
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.
My solution before wathcing the video (100% & 69%):
public boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
char leftChar, rightChar;
while (l < r) {
leftChar = s.charAt(l);
rightChar = s.charAt(r);
if ((leftChar < 'A' || (leftChar > 'Z' && leftChar < 'a') || leftChar > 'z') && !(leftChar >= '0' && leftChar 'Z' && rightChar < 'a') || rightChar > 'z') && !(rightChar >= '0' && rightChar = 'A' && leftChar = 'A' && rightChar
having 2 while loop in this case == O(n²) time?
Why is this problem disliked so much?
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 💀🃏
def isPalindrome(self, s: str) -> bool:
s = [c.lower() for c in s if c.isalnum()]
return s[:] == s[::-1]
Noob here, why can't you just import regex, lower case everything, filter out non a-z0-9 characters and then reverse a copy of a list.
import re
class Solution:
def isPalindrome(self, s: str) -> bool:
s = s.lower()
s = re.sub(r'[^a-z0-9]', '', s)
srev = s[::-1]
if s == srev:
return True
else:
return False
Simple solution in TypeScript using RegEx:
function isPalindrome(s: string): boolean {
const alphanumericOnly = s.replace(/[^a-zA-Z0-9]/g, "").toLowerCase();
const reversed = alphanumericOnly.split("").reverse().join("");
return alphanumericOnly === reversed;
}
def alphaNum(c):
return (('a'
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.
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
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.
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