Valid Palindrome - Leetcode 125 - Python

  Рет қаралды 278,716

NeetCode

NeetCode

Күн бұрын

Пікірлер: 171
@callmebiz
@callmebiz 3 жыл бұрын
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 :)
@NeetCode
@NeetCode 3 жыл бұрын
Good luck Stephen, you're gonna do great!
@friction5001
@friction5001 3 жыл бұрын
Good luck bro
@hs9577
@hs9577 2 жыл бұрын
howd it go!!??
@nero9985
@nero9985 2 жыл бұрын
Did you get the role?
@callmebiz
@callmebiz 2 жыл бұрын
@@nero9985 never interviewed, the recruiters kept me in limbo so long until I took a job elsewhere
@davidfranke6178
@davidfranke6178 Жыл бұрын
It's so damn satisfying having done a solution and seeing that Neetcode uses the absolute same method.
@amanzishan8399
@amanzishan8399 4 ай бұрын
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
@HowToAiNow
@HowToAiNow Жыл бұрын
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.
@akshaydusad6642
@akshaydusad6642 8 ай бұрын
That explains why the inbuilt methods are almost always faster than my custom ones.
@khanf13
@khanf13 3 ай бұрын
interesting!
@Extremesarova
@Extremesarova 2 жыл бұрын
Actually, we can write function for checking alphanumeric characters like this and it will work def isalnum(c: str) -> bool: return (("a"
@turtlenekk4354
@turtlenekk4354 2 жыл бұрын
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"
@Extremesarova
@Extremesarova 2 жыл бұрын
@@turtlenekk4354 I think that either solution is ok. If you can show several ways of doing the same thing it would be even better
@mp3ifier
@mp3ifier Жыл бұрын
Did not know this about python, thank you!
@vasileperciuleac1855
@vasileperciuleac1855 Жыл бұрын
just tried it - good to know! thx
@snooow2879
@snooow2879 Жыл бұрын
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🥴
@turtlenekk4354
@turtlenekk4354 2 жыл бұрын
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
@pinakadhara7650
@pinakadhara7650 2 жыл бұрын
This is a good idea. Reduces the code complexity!
@harperbye
@harperbye Жыл бұрын
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)
@Atom1794
@Atom1794 Жыл бұрын
@@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 :)
@prasid33
@prasid33 Жыл бұрын
i think this won't work for this: s= "AB{[BA"
@InfinityOver0
@InfinityOver0 28 күн бұрын
@@prasid33 It works. L = R on the last iteration of the while loop, so the loop breaks and True is returned.
@johns3641
@johns3641 3 жыл бұрын
Yes!!! Thank you for continuing with the LC 75 series!! We all really appreciate it.
@youngmoneymahini
@youngmoneymahini Жыл бұрын
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:...)
@eteran23
@eteran23 Жыл бұрын
Yeah, but you change the L and R values within the internal while loops, so you need to check again.
@mooglemog4726
@mooglemog4726 8 ай бұрын
If the string only has symbols you are cooked
@Lachlan1806
@Lachlan1806 Ай бұрын
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.
@nero9985
@nero9985 2 жыл бұрын
I'd let out a big sigh if the interviewer asked for another approach after I show him the first solution
@lucianoprokilla
@lucianoprokilla 7 ай бұрын
Abaha fr
@AustinCS
@AustinCS 24 күн бұрын
I mean, it's fair bc the cleaning method is bounded by the sum of natural numbers leading to a polynomial runtime.
@danielniels22
@danielniels22 13 күн бұрын
@@AustinCSwhat do you mean by this?
@AustinCS
@AustinCS 12 күн бұрын
​@@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!
@adventurer2395
@adventurer2395 2 жыл бұрын
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
@wasbashing
@wasbashing 3 жыл бұрын
I picked up blind-75 aswell! Keep up the grind as always 💪
@Xush11kkkk
@Xush11kkkk 14 күн бұрын
Helpful video. One can also perform a regex check to make sure the character values are in the alphanumeric range
@DonJulio-hr2uj
@DonJulio-hr2uj 7 ай бұрын
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.
@AustinCS
@AustinCS 24 күн бұрын
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.
@SteeleJackson2
@SteeleJackson2 10 ай бұрын
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
@johns3641
@johns3641 3 жыл бұрын
After LC 75 is done, can you do the SeanPrashad 170 questions? If you have both playlists, that would be HUGE
@showmethemoney824
@showmethemoney824 2 жыл бұрын
+1 to this ... can we do this?
@rishav-ranjan
@rishav-ranjan 2 жыл бұрын
@@showmethemoney824 +1
@crikxouba
@crikxouba 9 ай бұрын
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.
@taroserigano6546
@taroserigano6546 2 жыл бұрын
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
@gopalchavan306
@gopalchavan306 2 жыл бұрын
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; }
@ankushsarkar1746
@ankushsarkar1746 Жыл бұрын
yeah, was thinking the same
@someone3706
@someone3706 Жыл бұрын
@@mikelexx2542 it is not O(n^2) it is still O(n)
@재재재-m7r
@재재재-m7r Жыл бұрын
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..
@messiworldcupwinner
@messiworldcupwinner Жыл бұрын
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.
@byte_easel
@byte_easel 9 ай бұрын
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
@m_jdm357
@m_jdm357 5 ай бұрын
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.
@sf-spark129
@sf-spark129 Жыл бұрын
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
@LightningRod
@LightningRod 2 жыл бұрын
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!
@TethiusMC
@TethiusMC 2 жыл бұрын
How did you get past the "0P" case? It keeps failing for me there with set.
@Adam-hm2dz
@Adam-hm2dz 2 жыл бұрын
@@TethiusMC use .isalnum instead of .isalpha
@Yougottacryforthis
@Yougottacryforthis Жыл бұрын
this is actually bad practice but i guess LC baits you into writing bad code sometimes
@LightningRod
@LightningRod Жыл бұрын
@@Yougottacryforthis Can you elaborate?
@someone3706
@someone3706 Жыл бұрын
@@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
@andrescabezas2124
@andrescabezas2124 2 жыл бұрын
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.
@negaaa5080
@negaaa5080 2 жыл бұрын
But it will create a new string right?
@andrescabezas2124
@andrescabezas2124 2 жыл бұрын
@@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.
@pinakadhara7650
@pinakadhara7650 2 жыл бұрын
Same here!
@ArvyRV
@ArvyRV Жыл бұрын
The whole basis for the second solution was a space-time trade off for O(1) additional space from the start though.
@mikebean.
@mikebean. 3 жыл бұрын
whats next for the channel once you finish the 75 list?
@AdityaKumar-ec5th
@AdityaKumar-ec5th 10 ай бұрын
thank you neetcode
@Kitsune_Dev
@Kitsune_Dev 7 ай бұрын
why not convert the input string to lower from start? is it because that would cause more memory?
@hwang1607
@hwang1607 Жыл бұрын
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]
@ninadmuranjan1676
@ninadmuranjan1676 Жыл бұрын
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; };
@shaguntripathi8415
@shaguntripathi8415 11 ай бұрын
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
@vert_sr
@vert_sr 3 жыл бұрын
youre the goat man, do you have a linkedin?
@EranM
@EranM 7 ай бұрын
string concatenation is not really happening in python as string is immutable. Better to store all in list and then "".join(lst)
@Firecloak
@Firecloak 2 жыл бұрын
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
@ohhellnooooo8233
@ohhellnooooo8233 2 жыл бұрын
you can just return s == s[::-1]: no need for if else return true false
@Firecloak
@Firecloak 2 жыл бұрын
@@ohhellnooooo8233 oh nice, thank you!!
@doodlenoodle6685
@doodlenoodle6685 7 ай бұрын
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')
@anjalivas1111
@anjalivas1111 4 ай бұрын
Thank you so much!
@jayashreepoojaryy
@jayashreepoojaryy 2 жыл бұрын
When you find Neetcode's solution for your search on youtube..Happiness >>>>>
@rod6722
@rod6722 3 күн бұрын
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; }
@sajalsharma3931
@sajalsharma3931 11 ай бұрын
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.
@antoniocipriano1070
@antoniocipriano1070 10 ай бұрын
can you show ur solution for this. I am also running into the same failure for these testcases.
@sajalsharma3931
@sajalsharma3931 10 ай бұрын
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
@adityapillai3091
@adityapillai3091 10 ай бұрын
Isn't two while loops O(N^2)? Why are we using that when we can do this in O(N)?
@leafhurricane30
@leafhurricane30 3 ай бұрын
interviewer could also ask to not use character.lower() inbuilt function
@lingyuhu4623
@lingyuhu4623 2 жыл бұрын
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?
@gianniprocida3332
@gianniprocida3332 2 жыл бұрын
Excellent explanation
@amrabdelatyfathallah2487
@amrabdelatyfathallah2487 7 ай бұрын
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')
@kpio629
@kpio629 2 жыл бұрын
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?
@beyondpar.
@beyondpar. 2 жыл бұрын
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
@AnubhavApurva
@AnubhavApurva Жыл бұрын
can we add equality in the while statement: l
@jameshizon4861
@jameshizon4861 3 жыл бұрын
I was wondering why O(N) and not O(N^2) because of nested while loop.
@corycharpentier974
@corycharpentier974 3 жыл бұрын
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.
@anwarmohammad5795
@anwarmohammad5795 2 жыл бұрын
its not n^2 because we are visiting each element only once
@martinemanuel8239
@martinemanuel8239 2 жыл бұрын
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)
@montgomeryscottbrea2614
@montgomeryscottbrea2614 2 жыл бұрын
I'm probably going to name my first child after you if I get the job.
@NeetCode
@NeetCode 2 жыл бұрын
lol
@anantprakashsingh8777
@anantprakashsingh8777 2 жыл бұрын
You're gonna name your child "Neet"?
@PremPal-uy4nm
@PremPal-uy4nm Жыл бұрын
@@anantprakashsingh8777sounds cool though!
@friction5001
@friction5001 3 жыл бұрын
Great video
@abdullahmahi4490
@abdullahmahi4490 Жыл бұрын
I am facing this problem : TypeError: ord() expected string of length 1, but int found
@sriramadithya4799
@sriramadithya4799 2 жыл бұрын
This problem teaches me a lot of useful things
@geekydanish5990
@geekydanish5990 2 жыл бұрын
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
@cameronleverett7131
@cameronleverett7131 2 жыл бұрын
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]
@japanboy31415
@japanboy31415 5 ай бұрын
in the question howd u know you can ignore the punctuation ?
@riteeshacomputerscience4862
@riteeshacomputerscience4862 Жыл бұрын
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 !
@yombabwe3954
@yombabwe3954 Жыл бұрын
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
@sarahnguyen8117
@sarahnguyen8117 Жыл бұрын
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.
@byte_easel
@byte_easel 9 ай бұрын
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.
@bbg126
@bbg126 Жыл бұрын
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?
@Vagabond625
@Vagabond625 Жыл бұрын
just in case an interviewer doesn't what you to use built in functions like that
@haru5214
@haru5214 Жыл бұрын
I am getting type error for alphaNum function It saying '
@Ds10733
@Ds10733 11 ай бұрын
I used two pointers but with Regex.. is it bad?
@league83
@league83 3 жыл бұрын
really good one
@allstar965
@allstar965 7 ай бұрын
Beautiful solution
@jugsma6676
@jugsma6676 6 ай бұрын
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
@prasid33
@prasid33 Жыл бұрын
If s= "AB{[BA" Code works but still it won't shift the r to 2nd position
@prathyushakadali3330
@prathyushakadali3330 3 ай бұрын
Hi, thanks so much for sharing this. QQ around l==r case incase of odd number of characters, don't you think thats required?
@amazing-graceolutomilayo5041
@amazing-graceolutomilayo5041 3 жыл бұрын
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!!
@rebeccatom2188
@rebeccatom2188 Жыл бұрын
Why not just use the method, .alnum(), instead of making a helper function? What implications does that have for time and space complexity
@wew8820
@wew8820 2 жыл бұрын
so much info in such a short video
@pfiter6062
@pfiter6062 Жыл бұрын
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?
@pfiter6062
@pfiter6062 Жыл бұрын
I was wrong about it, the 2nd approach still iterates through the entire string
@byte_easel
@byte_easel 9 ай бұрын
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.
@prosodyspeaks4036
@prosodyspeaks4036 2 жыл бұрын
thanks! but why is it ok to use builtin .lower() but not builtin .alnum()?
@Atom1794
@Atom1794 Жыл бұрын
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
@michaelosorio2754
@michaelosorio2754 6 ай бұрын
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.
@deep9579
@deep9579 2 жыл бұрын
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
@JeffRagusa
@JeffRagusa 2 жыл бұрын
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.
@deep9579
@deep9579 2 жыл бұрын
@@JeffRagusa right...later I found that way also....👍😀 But totally forgot to update here
@bigkurz
@bigkurz Жыл бұрын
nice solution thank you
@richer7451
@richer7451 Жыл бұрын
Why does this question have so many downvotes on leetcode?
@xxvolcomxx56
@xxvolcomxx56 Ай бұрын
technically the first solution is faster because you wrote it faster
@Techgether
@Techgether 5 ай бұрын
having 2 while loop in this case == O(n²) time?
@ryujiganaha9645
@ryujiganaha9645 5 ай бұрын
Thank you!
@ianokay
@ianokay Жыл бұрын
In this solution won't "a!@#$" return true and "ab!@#$" return false due to the nature of the inc/dec while loops? 🤔
@Vagabond625
@Vagabond625 Жыл бұрын
"ab!@#$" will just be ab which is not a palindrome so it should return false. what am I missing?
@seifeddine3735
@seifeddine3735 2 жыл бұрын
we have loop inside loop how the time complexity could be o(n)???
@tzujuiyu
@tzujuiyu 2 жыл бұрын
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)
@vinaynaik953
@vinaynaik953 3 жыл бұрын
Superb
@efenestration
@efenestration 11 ай бұрын
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 💀🃏
@draugno7
@draugno7 Ай бұрын
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
@dharmendra.pandit
@dharmendra.pandit Ай бұрын
def alphaNum(c): return (('a'
@kirillzlobin7135
@kirillzlobin7135 4 ай бұрын
Great!
@tanujshriyan
@tanujshriyan 2 жыл бұрын
Could someone explain me why r = len(s)-1.. why -1 is used?
@eduardofernandes9998
@eduardofernandes9998 2 жыл бұрын
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.
@tanujshriyan
@tanujshriyan 2 жыл бұрын
@@eduardofernandes9998 Thank you so much
@gouravkumarshaw417
@gouravkumarshaw417 2 жыл бұрын
thanks !!
@devmahad
@devmahad Ай бұрын
thanks :)
@indhumathi5846
@indhumathi5846 Жыл бұрын
understood
@davidbujosa
@davidbujosa Жыл бұрын
Thanks u
@anush8
@anush8 Жыл бұрын
def isPalindrome(self, s: str) -> bool: s = [c.lower() for c in s if c.isalnum()] return s[:] == s[::-1]
@SteeleJackson2
@SteeleJackson2 10 ай бұрын
13:58
@AR-go4qz
@AR-go4qz 2 жыл бұрын
Why is this problem disliked so much?
@minh355
@minh355 Ай бұрын
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
@valentinrafael9201
@valentinrafael9201 5 ай бұрын
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.
@sidersoorma
@sidersoorma Жыл бұрын
we can use .isalnum() for checking if the number is alpha numeric, and thanks for the series blind75 compilation.
@sjzz
@sjzz Жыл бұрын
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())
@minciNashu
@minciNashu 2 жыл бұрын
Python has built-in utility to check alphanumeric: str.isalnum() That leetcode benchmark is not reliable, you can submit repeatedly and get varying results.
@smtp_yurzx
@smtp_yurzx Жыл бұрын
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
@unikaang1177
@unikaang1177 Жыл бұрын
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.🥲
@vinaynaik953
@vinaynaik953 3 жыл бұрын
Superb
Making an Algorithm Faster
30:08
NeetCodeIO
Рет қаралды 148 М.
How I would learn Leetcode if I could start over
18:03
NeetCodeIO
Рет қаралды 688 М.
How To Choose Mac N Cheese Date Night.. 🧀
00:58
Jojo Sim
Рет қаралды 89 МЛН
Увеличили моцареллу для @Lorenzo.bagnati
00:48
Кушать Хочу
Рет қаралды 8 МЛН
Каха и лужа  #непосредственнокаха
00:15
БУ, ИСПУГАЛСЯ?? #shorts
00:22
Паша Осадчий
Рет қаралды 2,9 МЛН
Python for Coding Interviews - Everything you need to Know
26:18
Beginners Should Think Differently When Writing Golang
11:35
Anthony GG
Рет қаралды 123 М.
Premature Optimization
12:39
CodeAesthetic
Рет қаралды 834 М.
LeetCode was HARD until I Learned these 15 Patterns
13:00
Ashish Pratap Singh
Рет қаралды 577 М.
10 Math Concepts for Programmers
9:32
Fireship
Рет қаралды 1,9 МЛН
How to Solve ANY LeetCode Problem (Step-by-Step)
12:37
Codebagel
Рет қаралды 300 М.
Dependency Injection, The Best Pattern
13:16
CodeAesthetic
Рет қаралды 883 М.
How To Choose Mac N Cheese Date Night.. 🧀
00:58
Jojo Sim
Рет қаралды 89 МЛН