Valid Palindrome - Leetcode 125 - Python

  Рет қаралды 267,152

NeetCode

3 жыл бұрын

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: neetcode1
🥷 Discord: discord.gg/ddjKRXPqtk
🐮 Support the channel: www.patreon.com/NEETcode
✔️ SPREADSHEET BLIND-75: docs.google.com/spreadsheets/d/1A2PaQKcdwO_lwxz9bAnxXnIQayCouZP6d-ENrBz_NXc/edit#gid=0
⭐ BLIND-75 PLAYLIST: kzbin.info/www/bejne/gX3PiXZ8fJqHpKM
💡 CODING SOLUTIONS: kzbin.info/aero/PLot-Xpze53leF0FeHz2X0aG3zd0mr1AW_
💡 DYNAMIC PROGRAMMING PLAYLIST: kzbin.info/www/bejne/bWTVZH6Nnqqpr80
🌲 TREE PLAYLIST: kzbin.info/www/bejne/hZ-2n2WOerZng7s
💡 GRAPH PLAYLIST: kzbin.info/www/bejne/e5isZqGLbsqnpLc
💡 BACKTRACKING PLAYLIST: kzbin.info/www/bejne/ppfMgpKGiJaabqc
💡 LINKED LIST PLAYLIST: kzbin.info/www/bejne/fWHCemCQe5WGaZo
💡 BINARY SEARCH PLAYLIST: kzbin.info/aero/PLot-Xpze53leNZQd0iINpD-MAhMOMzWvO
📚 STACK PLAYLIST: kzbin.info/aero/PLot-Xpze53lfxD6l5pAGvCD4nPvWKU8Qo
Problem Link: neetcode.io/problems/is-palindrome
0:00 - Read the problem
1:40 - Explaining Solution #1
3:45 - Coding Solution #1
5:40 - Explaining Solution #2
9:35 - Coding Solution #2
leetcode 125
This question was identified as an interview question from here: github.com/xizhengszhang/Leetcode_company_frequency
#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

Пікірлер: 164
@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 3 ай бұрын
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 11 ай бұрын
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 7 ай бұрын
That explains why the inbuilt methods are almost always faster than my custom ones.
@khanf13
@khanf13 2 ай бұрын
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 Жыл бұрын
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"
@johns3641
@johns3641 3 жыл бұрын
Yes!!! Thank you for continuing with the LC 75 series!! We all really appreciate it.
@wasbashing
@wasbashing 3 жыл бұрын
I picked up blind-75 aswell! Keep up the grind as always 💪
@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 11 ай бұрын
Yeah, but you change the L and R values within the internal while loops, so you need to check again.
@mooglemog4726
@mooglemog4726 6 ай бұрын
If the string only has symbols you are cooked
@Lachlan1806
@Lachlan1806 11 күн бұрын
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 6 ай бұрын
Abaha fr
@adventurer2395
@adventurer2395 Жыл бұрын
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
@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
@SteeleJackson2
@SteeleJackson2 9 ай бұрын
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
@DonJulio-hr2uj
@DonJulio-hr2uj 6 ай бұрын
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.
@재재재-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 8 ай бұрын
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
@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)
@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 Жыл бұрын
@@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
@crikxouba
@crikxouba 8 ай бұрын
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.
@Kitsune_Dev
@Kitsune_Dev 6 ай бұрын
why not convert the input string to lower from start? is it because that would cause more memory?
@vert_sr
@vert_sr 3 жыл бұрын
youre the goat man, do you have a linkedin?
@m_jdm357
@m_jdm357 4 ай бұрын
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.
@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 Жыл бұрын
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?
@adityapillai3091
@adityapillai3091 9 ай бұрын
Isn't two while loops O(N^2)? Why are we using that when we can do this in O(N)?
@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?
@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!
@haru5214
@haru5214 Жыл бұрын
I am getting type error for alphaNum function It saying '
@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 !
@abdullahmahi4490
@abdullahmahi4490 11 ай бұрын
I am facing this problem : TypeError: ord() expected string of length 1, but int found
@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
@doodlenoodle6685
@doodlenoodle6685 6 ай бұрын
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 3 ай бұрын
Thank you so much!
@jayashreepoojaryy
@jayashreepoojaryy 2 жыл бұрын
When you find Neetcode's solution for your search on youtube..Happiness >>>>>
@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 10 ай бұрын
just in case an interviewer doesn't what you to use built in functions like that
@AnubhavApurva
@AnubhavApurva Жыл бұрын
can we add equality in the while statement: l
@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
@japanboy31415
@japanboy31415 3 ай бұрын
in the question howd u know you can ignore the punctuation ?
@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
@prathyushakadali3330
@prathyushakadali3330 2 ай бұрын
Hi, thanks so much for sharing this. QQ around l==r case incase of odd number of characters, don't you think thats required?
@sajalsharma3931
@sajalsharma3931 9 ай бұрын
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 9 ай бұрын
can you show ur solution for this. I am also running into the same failure for these testcases.
@sajalsharma3931
@sajalsharma3931 9 ай бұрын
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
@AdityaKumar-ec5th
@AdityaKumar-ec5th 9 ай бұрын
thank you neetcode
@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 11 ай бұрын
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 8 ай бұрын
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.
@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!!
@Ds10733
@Ds10733 10 ай бұрын
I used two pointers but with Regex.. is it bad?
@jameshizon4861
@jameshizon4861 3 жыл бұрын
I was wondering why O(N) and not O(N^2) because of nested while loop.
@corycharpentier974
@corycharpentier974 2 жыл бұрын
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)
@shaguntripathi8415
@shaguntripathi8415 10 ай бұрын
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
@gianniprocida3332
@gianniprocida3332 2 жыл бұрын
Excellent explanation
@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
@0yustas0
@0yustas0 2 жыл бұрын
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]
@negaaa5080
@negaaa5080 2 жыл бұрын
Less number of lines doesn't equals more efficient
@SteeleJackson2
@SteeleJackson2 9 ай бұрын
this solution is probably O(n!) time lmao
@EranM
@EranM 6 ай бұрын
string concatenation is not really happening in python as string is immutable. Better to store all in list and then "".join(lst)
@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; };
@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
@friction5001
@friction5001 3 жыл бұрын
Great video
@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]
@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!!
@sriramadithya4799
@sriramadithya4799 2 жыл бұрын
This problem teaches me a lot of useful things
@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]
@vinaynaik953
@vinaynaik953 3 жыл бұрын
Superb
@league83
@league83 3 жыл бұрын
really good one
@leafhurricane30
@leafhurricane30 2 ай бұрын
interviewer could also ask to not use character.lower() inbuilt function
@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 10 ай бұрын
"ab!@#$" will just be ab which is not a palindrome so it should return false. what am I missing?
@allstar965
@allstar965 6 ай бұрын
Beautiful solution
@wew8820
@wew8820 2 жыл бұрын
so much info in such a short video
@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)
@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 8 ай бұрын
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.
@prasid33
@prasid33 Жыл бұрын
If s= "AB{[BA" Code works but still it won't shift the r to 2nd position
@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
@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
@bigkurz
@bigkurz 11 ай бұрын
nice solution thank you
@amrabdelatyfathallah2487
@amrabdelatyfathallah2487 5 ай бұрын
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')
@ryujiganaha9645
@ryujiganaha9645 4 ай бұрын
Thank you!
@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
@Techgether
@Techgether 4 ай бұрын
having 2 while loop in this case == O(n²) time?
@jugsma6676
@jugsma6676 5 ай бұрын
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
@richer7451
@richer7451 Жыл бұрын
Why does this question have so many downvotes on leetcode?
@michaelosorio2754
@michaelosorio2754 4 ай бұрын
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.
@kirillzlobin7135
@kirillzlobin7135 3 ай бұрын
Great!
@gouravkumarshaw417
@gouravkumarshaw417 2 жыл бұрын
thanks !!
@SteeleJackson2
@SteeleJackson2 9 ай бұрын
13:58
@devmahad
@devmahad 12 күн бұрын
thanks :)
@efenestration
@efenestration 9 ай бұрын
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 💀🃏
@davidbujosa
@davidbujosa Жыл бұрын
Thanks u
@indhumathi5846
@indhumathi5846 Жыл бұрын
understood
@AR-go4qz
@AR-go4qz 2 жыл бұрын
Why is this problem disliked so much?
@anush8
@anush8 Жыл бұрын
def isPalindrome(self, s: str) -> bool: s = [c.lower() for c in s if c.isalnum()] return s[:] == s[::-1]
@minh355
@minh355 7 күн бұрын
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
@dharmendra.pandit
@dharmendra.pandit 6 күн бұрын
def alphaNum(c): return (('a'
@sidersoorma
@sidersoorma Жыл бұрын
we can use .isalnum() for checking if the number is alpha numeric, and thanks for the series blind75 compilation.
@valentinrafael9201
@valentinrafael9201 3 ай бұрын
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.
@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())
@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
@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.
@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
小蚂蚁会选到什么呢!#火影忍者 #佐助 #家庭
00:47
火影忍者一家
Рет қаралды 105 МЛН
ТИПИЧНОЕ ПОВЕДЕНИЕ МАМЫ
00:21
SIDELNIKOVVV
Рет қаралды 1,4 МЛН
Inside Out 2: ENVY & DISGUST STOLE JOY's DRINKS!!
00:32
AnythingAlexia
Рет қаралды 18 МЛН
Секретные процессоры!
0:27
CONSTRUCT PC
Рет қаралды 523 М.
The force of electromagnetic eddy currents
0:31
Nikola Toy
Рет қаралды 34 МЛН
Как остановить электрический счетчик импульсным прибором
0:23
Остановка счетчика на воду, газ, электричество
Рет қаралды 1,5 МЛН
Самый дорогой iPHONE 16 PRO MAX #shorts
0:58
Арсений Петров
Рет қаралды 3,1 МЛН
iPhone теперь БЕСПОЛЕЗНО воровать 🛠
0:25
Technodeus
Рет қаралды 1,3 МЛН