This Solution can be optimized by using a memoization to store all the correct palindromes and the false ones so we only have to check the same substring in only O(1) time using a hashmap or a 2d array
But each partition is different There could be a possibility that we may get luckily a same string for checking isn't? Please help me to understand
ปีที่แล้ว +2
@@BishalECE-uy5rnImagine a situation where the first half of the string can be partitioned in X ways and the second part can be partitioned in Y ways. Motivation will help you avoid recomputing the second half X times again and again
It depends on if you want memory efficiency or runtime efficiency. Memoizing checked substrings will incur O(n^2) additional memory (since there’s O(n^2) possible substrings), but will save you O(n^3) additional runtime (isPali runs in O(n) per substring)
I concur! anyone can explains why its 2^n? I have read in leetcode solutions where some said there's 2 recursive calls on each iteration but in the code it is calling "for range" calls instead.
Hi, I have watched some of your videos and tried to solve this problem by myself this time, amazingly it works!, I can not believe I solve it in five minutes. it's another way so I put it here. class Solution(object): def partition(self, s): """ :type s: str :rtype: List[List[str]] """ # My solution !!!!!!!!!!!!!!!!!!!!!!!!!!!!!! res=[]
def dfs(s,palin): if len(s)==0: res.append(palin[:]) else: for i in range(len(s)): if s[:i+1]==s[:i+1][::-1]: palin.append(s[:i+1]) print(s[:i+1]) dfs(s[i+1:],palin) palin.pop()
I spent a day thinking over this problem but couldn't think of the right solution.. it feels really annoying and almost feel like giving up.. don't think I can ever master this sorcery!
I felt like that too. We just need to remember that it probably took Computer Scientists years to figure out these techniques. For the rest of us, it just takes practice my friend :-)
it's more about how well you understand it (backtracking in this case) I'm doing neetcode all, reached backtracking and this is the 9th problem, took me 50 min (timed on leetcode) to finish it and write a quick summary + thinking about time complexity (which admittedly I couldn't figure out precisely) if you think carefully about what it asks and create a decision tree to visualize it you should have a vague idea and if you solved the previous problems it's easier
I initially started by finding all the possible palindrome substrings (i guess I need to pay more attention to the examples and instructions). The hardest part of this problem was understanding the desired output :p
I tried submitting a solution of mine on the NeetCode compiler, it did not accept the answer in different order. Since it is mentioned return in any order, all orders should have been accepted. Just thought I should share this feedback. Huge fan of your knowledge and all the help you are providing to us newbies!
Tricky question with wording, I originally thought it was saying it is a valid palindrome if letters can be rearranged to be a palindrome, but really it's the raw string being a palindrome. Getting better at these though, backtracking definitely has a common format.
hey could you make a solution for Palindrome Partitioning II as well(leetcode 132)? got stucked there for days due to TLE. your video is always the most helpful one :)
@neetcode you put the video chapters in the wrong location FYI. You marked the "coding explanation" 30+ seconds after the coding begins, I think because you reference back to the drawing during the coding?
I believe the copy was made because if you end up modifying the part list in a different function it will modify the res list incorrectly. There is only one version of the list, to keep with consistency in that function you will create that copy
Judging from the way he said that, I don't think he understands the time complexity for this code. He just generically knows to say 2^n whenever he goes over all the possibilities
It's so hard to mentally walk through the exact path on these kinds of problems, with the falling through (and before that meeting conditions and not meeting conditions, entering and not entering new stacks and pushing and popping from shared references).
I'm still struggling to understand how to choose what to do at each step in the DFS. Like how do I know that I need to split my decision in such a way as described in the video?
For me, I think about how I can isolate unique answers. When I have an idea, I sketch out the tree and see if my logic holds. For this one I started out thinking I could split my decisions based on which side of the partition a character was on. For the first character "a" for instance, I was thinking it could be "a |" or "| a". I tried sketching out the tree but it got messy because for the second "a" I was getting duplicates (e.g. if second "a" goes on right or left I got "aa |" and " | aa"). My next approach was to fix the first n characters, and I saw that "a", "aa" and "aab" could define unique splits. I then realized this logic would hold recursively as well and that once I fixed the first n characters, I could define similar unique splits for the remaining (m - n) characters where m is the size of input the string. If you don't already draw like Neetcode does in the videos, I highly recommend using whiteboard and / or pen and paper before writing any code.
anyone else confused by what is meant by a "substring of a partition"? for example: "aa | b" us a partition, and substring of this may imply "a", "a, a", and "b" ?
Confused about the time complexity. the way that your tree is drawn, it is hard to see the 2^x at each level, capping off with 2^n at the very end. Intuitive, I see that each level could have ~n^x , capping off at n^n.
Isn’t it possible to just use “palindromic substrings” with the dp solution in O(n^2) time combined with backtracking (which would be slightly more efficient since we know the palindromic substrings already)? We can also find the substrings in O(n) time with cool algos too
Yes, I too was thinking the same. We can have a dp boolean array such that it is true if the substring is palindrome. This will be more efficient since we wont have to compute the isPal again and again
Can you tell me if I am doing right? Sometimes, I come up with a solution for which few test cases fail and I reach a dead end where I cannot improve it further then I have to look at a solution. Is it expected that I should always come up with the solution myself or there are other people like me and it is okay
I think it's okay to look at solutions for new problems. That's how I learned most of my knowledge, eventually you will be able to figure out most problems on your own.
That's kinda like my case. I always try to come up with a workable solution on my own, even if it's brute force, otherwise I would feel dumb and disappointed at myself. I would end up spending hours on a medium even easy question, and would only refer to a solution when I exhaust every possible way and have nowhere to go. I know it's very inefficient but meanwhile hard to convince myself to look directly at solutions if I'm stuck for 10 minutes.
@@AndrewCJXing Just gotta realize that computer science researchers took years (and were paid) to find these solutions. It doesn't make sense to re-invent the wheel, gotta stand on the shoulders of giants.
after finding the first res [a, a, b] we reached the base case because i = 3 and i == len(s) we return to the previous call stack i = 2 j = 2 the 'b' is popped from cur i thought that was sufficient, because we only did one return which is from the base case but how come we return to the previous call stack i = 1 j = 1 from i = 2 j = 2 and popped 'a' from cur too??
let's say input is "aabb". so at index 0 when we will make a check to see if partition 0 -> 3, i.e. "aabb | " is valid ? the palindrome checker will say true, go ahead it's valid. then dfs(4) will be called and this "aabb" would pass the base check and should be appended to res. BUT BUT BUT how come i don't see "aabb |" in answer ? what part of code is preventing it ? .... like i do know the expected solution does not want "aabb |" as answer, but how is the code making sure of it ? where ? because ideally this code should be including "aabb | " to it's answer as well..
You need to clean up your current path array so that the next iteration of the for loop does not have extra substrings in it. If you didn't pop, then the the solution for each subsequent substring in the for loop would have extra substrings in it. in the example give it would return [["a" ,"a", "b"], ["a" ,"aa", "b"]] if you were passing in the result as an argument. But in his example he isn't even passing result as an argument or by reference so the second output would have the first string vector in the result i.e. [["a","a","b"],["a","a","b","aa","b"]]. Hope this explanation helps.
@@alexm1930 Can you help? i have written code in javascript but i cant find a way to mimic python "copy" function. it returns "aa, a, b" in second partition.
It's a step in backtracking algorithms to undo something. In this case, his code removes the palindrome substring that was added to the 'part' array on line 12 so that he can try a different palindrome on the next iteration of the loop.
I wrote a sol but I am having trouble identify it's time complexity! Please help. #Using recursive approach def partition(self, s: str) -> List[List[str]]: if not s : #Base case return [deque()] output = []
for i in range(len(s)) : curr = s[:i+1] #getting all the first partitions possible if curr == curr[::-1] : #if current partition is a palindrome res = self.partition(s[i+1:]) #s[i+1:] is a sub-problem, using recursive function to get correct output for ans in res : ans.appendleft(curr) output.extend(res) return output
@@daviduzumaki yes, but for each subpartition you have n again, not 2 branches. I found better explanation. for each n we have such function f(n) = f(n-1) + f(n-2) + f(n-3)... f(n - 1) = f(n-2) + f(n-3)... so f(n) =f(n-1) + f(n-1) f(n) = 2f(n - 1)
The way he drew the tree in the video was that he broke the string into 3 partitions such as "a", "aa, "aab" as in the roots, he initially checks to see if they are a palindrome to see if he needs to continue on. aab wasnt valid so he didnt move forward. Then further down the tree they linked using the next part of the string, thus again chekcking to see if those are palidromes. a -> aa, aa -> aab. then returning in the results list. I hope this make sense.
"a" "aa" "aab" are the initial partitions. in the next height of the tree you do see "a" -> "a" which i believe is your question of why theres not a repeating "a"
What is a partition? Is that a subarray? I don’t understand the question. Why would anybody ever want this? Obviously, we are not trying to build anything. I’m having a hard time stretching my imagination to see how this could ever be useful. I get that we have to learn these things because we need to pass interviews, but why? Isn’t it futile?
i've practiced more than 100 problems now on backtracking...but still i couldnt solve even an easy leetcode on my own :( dont know why god gave me such low IQ
💡 BACKTRACKING PLAYLIST: th-cam.com/video/pfiQ_PS1g8E/w-d-xo.html
You never jump to the solution directly that's what I like about this channel
Starting to see the template now for all these backtracking problems. You're great
Nice dude. Shortest and best explained solution I've encountered.
Thanks, much appreciated
This Solution can be optimized by using a memoization to store all the correct palindromes and the false ones so we only have to check the same substring in only O(1) time using a hashmap or a 2d array
the length of the string is
But each partition is different
There could be a possibility that we may get luckily a same string for checking isn't? Please help me to understand
@@BishalECE-uy5rnImagine a situation where the first half of the string can be partitioned in X ways and the second part can be partitioned in Y ways. Motivation will help you avoid recomputing the second half X times again and again
It depends on if you want memory efficiency or runtime efficiency. Memoizing checked substrings will incur O(n^2) additional memory (since there’s O(n^2) possible substrings), but will save you O(n^3) additional runtime (isPali runs in O(n) per substring)
if we use a hash map cache, what will be the resultant complexity? How do we derive complexity after using a cache?
Objection!! why is the time complexity is "2 over n". the decision tree has "width n" and "height n". it should "n over n"
n^n and we also should add time complexity of the checking if the given substring is the palindrome
I concur! anyone can explains why its 2^n? I have read in leetcode solutions where some said there's 2 recursive calls on each iteration but in the code it is calling "for range" calls instead.
You should use a cache for the palindrome function. Cache misses should try recursively do cache lookups for substrings too (i.e. start+1, end-1).
great explanation. thank you!! still having hard time wrapping my head around backtracking question ngl ://////////
You got this bruv :)
I thought of sliding window initially but couldn’t solve entirely. Thanks for the explanation
same
Hi, I have watched some of your videos and tried to solve this problem by myself this time, amazingly it works!, I can not believe I solve it in five minutes. it's another way so I put it here.
class Solution(object):
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
# My solution !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
res=[]
def dfs(s,palin):
if len(s)==0:
res.append(palin[:])
else:
for i in range(len(s)):
if s[:i+1]==s[:i+1][::-1]:
palin.append(s[:i+1])
print(s[:i+1])
dfs(s[i+1:],palin)
palin.pop()
dfs(s,[])
return res
I spent a day thinking over this problem but couldn't think of the right solution.. it feels really annoying and almost feel like giving up.. don't think I can ever master this sorcery!
I felt like that too. We just need to remember that it probably took Computer Scientists years to figure out these techniques. For the rest of us, it just takes practice my friend :-)
it's more about how well you understand it (backtracking in this case)
I'm doing neetcode all, reached backtracking and this is the 9th problem, took me 50 min (timed on leetcode) to finish it and write a quick summary + thinking about time complexity (which admittedly I couldn't figure out precisely)
if you think carefully about what it asks and create a decision tree to visualize it you should have a vague idea and if you solved the previous problems it's easier
No one does it better than you man! Thanks a lot
Your explanation is so clear and easy to follow.
absolutely awesome, thank you so much, I could finally understand thanks to your explanation
That is a really clever way to solve it!
Thank you for a great solution!
I initially started by finding all the possible palindrome substrings (i guess I need to pay more attention to the examples and instructions). The hardest part of this problem was understanding the desired output :p
THANK YOU for this simple explanation!
Thanks a lot! Better explanation than top leetcode solutions.
I tried submitting a solution of mine on the NeetCode compiler, it did not accept the answer in different order. Since it is mentioned return in any order, all orders should have been accepted. Just thought I should share this feedback. Huge fan of your knowledge and all the help you are providing to us newbies!
Tricky question with wording, I originally thought it was saying it is a valid palindrome if letters can be rearranged to be a palindrome, but really it's the raw string being a palindrome.
Getting better at these though, backtracking definitely has a common format.
Awsome coding, I wanted to do this question a similar fashion but was not getting the technique. Thank you
Wow, your explanations with the drawings are really good. Your explanations are really good. Thank you.
*Minor correction, the time complexity is not 2^n, it is n*2^n*
True! Because there is a palindrome check each time and the palindrome check is O(n)
Thanks
can u explain why it is even 2 to the power n ? like why isnt it n to the power n i cannot get it
@@Arthurgarzajr no its the copy..
@@majdalkwaja9792 how many leaf nodes aka paths does it have?
Great explanation✨,btw which code editor you used in this video?
its leetcode
I think you are asking for color theme. If you are, it's solarized dark.
@@AndrewCJXing Yeah.Thank you🤗
hey could you make a solution for Palindrome Partitioning II as well(leetcode 132)? got stucked there for days due to TLE. your video is always the most helpful one :)
Thank You So Much NeetCode brother.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@neetcode you put the video chapters in the wrong location FYI. You marked the "coding explanation" 30+ seconds after the coding begins, I think because you reference back to the drawing during the coding?
Returns [] instead of the expected output , checked it several times
make a copy of the part list, do not add it directly because part will be cleaned in the end
Clean and clear expalantion!
Q: Why time complexity is 2^n? I just failed to figure it out
its N*(2^N) see in leetcode soln tab
Amazing video!! Could you please explain why you used part.copy() instead of just part?
I believe the copy was made because if you end up modifying the part list in a different function it will modify the res list incorrectly. There is only one version of the list, to keep with consistency in that function you will create that copy
to check a palindrome string you can do something like: 'if s[i:j] == s[i:j][::-1]'
@@brandonwisco ur mom is slower
Can someone explain further why its O(2^n)
Judging from the way he said that, I don't think he understands the time complexity for this code. He just generically knows to say 2^n whenever he goes over all the possibilities
Great video, great explanation. Very educational. Thank you very much
It's so hard to mentally walk through the exact path on these kinds of problems, with the falling through (and before that meeting conditions and not meeting conditions, entering and not entering new stacks and pushing and popping from shared references).
I'm still struggling to understand how to choose what to do at each step in the DFS. Like how do I know that I need to split my decision in such a way as described in the video?
For me, I think about how I can isolate unique answers. When I have an idea, I sketch out the tree and see if my logic holds. For this one I started out thinking I could split my decisions based on which side of the partition a character was on. For the first character "a" for instance, I was thinking it could be "a |" or "| a". I tried sketching out the tree but it got messy because for the second "a" I was getting duplicates (e.g. if second "a" goes on right or left I got "aa |" and " | aa"). My next approach was to fix the first n characters, and I saw that "a", "aa" and "aab" could define unique splits. I then realized this logic would hold recursively as well and that once I fixed the first n characters, I could define similar unique splits for the remaining (m - n) characters where m is the size of input the string. If you don't already draw like Neetcode does in the videos, I highly recommend using whiteboard and / or pen and paper before writing any code.
This seems so simple after your explanation😭
anyone else confused by what is meant by a "substring of a partition"? for example: "aa | b" us a partition, and substring of this may imply "a", "a, a", and "b" ?
Yes, the question is extremely unclear.
@@spacetoast7783 It's because everyone writing the LeetCode questions don't speak Engrish.
Wouldn't the time complextiy be O(N*2^N) instead of O(2^N)? We are checking if each substring is palindrome in O(N) time.
Confused about the time complexity. the way that your tree is drawn, it is hard to see the 2^x at each level, capping off with 2^n at the very end. Intuitive, I see that each level could have ~n^x , capping off at n^n.
hey @NeetCode shouldn't the time-complexity be n^n?
Awesome explanation
Isn’t it possible to just use “palindromic substrings” with the dp solution in O(n^2) time combined with backtracking (which would be slightly more efficient since we know the palindromic substrings already)? We can also find the substrings in O(n) time with cool algos too
Yes, I too was thinking the same. We can have a dp boolean array such that it is true if the substring is palindrome. This will be more efficient since we wont have to compute the isPal again and again
I don't understand why we're popping from path and why we're only appending a copy of path to result
Could anyone explain why is it 2 to the power n
Can you tell me if I am doing right?
Sometimes, I come up with a solution for which few test cases fail and I reach a dead end where I cannot improve it further then I have to look at a solution.
Is it expected that I should always come up with the solution myself or there are other people like me and it is okay
I think it's okay to look at solutions for new problems. That's how I learned most of my knowledge, eventually you will be able to figure out most problems on your own.
That's kinda like my case. I always try to come up with a workable solution on my own, even if it's brute force, otherwise I would feel dumb and disappointed at myself. I would end up spending hours on a medium even easy question, and would only refer to a solution when I exhaust every possible way and have nowhere to go. I know it's very inefficient but meanwhile hard to convince myself to look directly at solutions if I'm stuck for 10 minutes.
@@AndrewCJXing Just gotta realize that computer science researchers took years (and were paid) to find these solutions. It doesn't make sense to re-invent the wheel, gotta stand on the shoulders of giants.
after finding the first res [a, a, b]
we reached the base case because i = 3 and i == len(s)
we return to the previous call stack i = 2 j = 2
the 'b' is popped from cur
i thought that was sufficient, because we only did one return which is from the base case
but how come we return to the previous call stack i = 1 j = 1 from i = 2 j = 2
and popped 'a' from cur too??
let's say input is "aabb". so at index 0 when we will make a check to see if partition 0 -> 3, i.e. "aabb | " is valid ? the palindrome checker will say true, go ahead it's valid. then dfs(4) will be called and this "aabb" would pass the base check and should be appended to res. BUT BUT BUT how come i don't see "aabb |" in answer ? what part of code is preventing it ? .... like i do know the expected solution does not want "aabb |" as answer, but how is the code making sure of it ? where ? because ideally this code should be including "aabb | " to it's answer as well..
Thanks for the visual champ
Ok so the actual time complexity is n * 2^n including the isPali check.
But why is it 2^n for the time complexity for the backtracking part?
awesome as usual!
Can you, please, exaplin why you do `part.pop()`? I can't wrap my head around it
You need to clean up your current path array so that the next iteration of the for loop does not have extra substrings in it. If you didn't pop, then the the solution for each subsequent substring in the for loop would have extra substrings in it. in the example give it would return [["a" ,"a", "b"], ["a" ,"aa", "b"]] if you were passing in the result as an argument. But in his example he isn't even passing result as an argument or by reference so the second output would have the first string vector in the result i.e. [["a","a","b"],["a","a","b","aa","b"]].
Hope this explanation helps.
@@alexm1930 Can you help? i have written code in javascript but i cant find a way to mimic python "copy" function. it returns "aa, a, b" in second partition.
@@Saurabhkumar-bn3dl In javascript, to make a copy (in this case it would be shallow) you would use the spread operator ( ex: res.push(...part) )
thanks for the video!
my head hurts trying to understand the time complexity of this algorithm
In this question in Example 1 "aab" why [["a","ab"]] is a valid one?
Where did they mention compulsary to take 1st character?
It doesn't say it is valid. I have no idea what you're seeing.
hiii would someone mind explaining why we are popping the last element? i can't visualize this step
Hi, did you understand this? Would you please explain it if you did?
It's a step in backtracking algorithms to undo something. In this case, his code removes the palindrome substring that was added to the 'part' array on line 12 so that he can try a different palindrome on the next iteration of the loop.
since when did neetcode go back to the explanation mid code 😔 man you were so cute
["aa"] alone wouldn't be a subset?
Thank you man
Useful video, ty
I wrote a sol but I am having trouble identify it's time complexity!
Please help.
#Using recursive approach
def partition(self, s: str) -> List[List[str]]:
if not s : #Base case
return [deque()]
output = []
for i in range(len(s)) :
curr = s[:i+1] #getting all the first partitions possible
if curr == curr[::-1] : #if current partition is a palindrome
res = self.partition(s[i+1:]) #s[i+1:] is a sub-problem, using recursive function to get correct output
for ans in res :
ans.appendleft(curr)
output.extend(res)
return output
U a God
no u
could someone explain why it is 2^n? at each step(the all steps are n) we don't do 2 branches, but n branches at most
@@daviduzumaki yes, but for each subpartition you have n again, not 2 branches.
I found better explanation.
for each n we have such function
f(n) = f(n-1) + f(n-2) + f(n-3)...
f(n - 1) = f(n-2) + f(n-3)...
so f(n) =f(n-1) + f(n-1)
f(n) = 2f(n - 1)
why is it 2^n time?
what's the reason for us to use for loop in our dfs function?
looping through all possible choices of dfs , visualize it as horizontal expansion
can anyone pls tell me why r we popping the partition from the ans
THE best.
why do we have to do part.pop() at the end?
"popping" is like going "up" in your decision tree. When you finished going thru a branch, you then need to backtrack - you do so by popping
@@logn-x5e damn bro , you replied after a year 😂. Appreciate it though
I am not able to visualize or draw the recursion tree
Please help anyone how to improve this
The way he drew the tree in the video was that he broke the string into 3 partitions such as "a", "aa, "aab" as in the roots, he initially checks to see if they are a palindrome to see if he needs to continue on. aab wasnt valid so he didnt move forward. Then further down the tree they linked using the next part of the string, thus again chekcking to see if those are palidromes. a -> aa, aa -> aab. then returning in the results list. I hope this make sense.
why are we not repeating 'a' character?
"a" "aa" "aab" are the initial partitions. in the next height of the tree you do see "a" -> "a" which i believe is your question of why theres not a repeating "a"
What is a partition? Is that a subarray? I don’t understand the question. Why would anybody ever want this? Obviously, we are not trying to build anything. I’m having a hard time stretching my imagination to see how this could ever be useful.
I get that we have to learn these things because we need to pass interviews, but why? Isn’t it futile?
part.pop() is very hard to understand.
genius
loop in a loop in a loop, you sure about this solution being optimum?
Hahaha... i thought there was a better way then brute force. I guess I was wrong
Best
131, palindrome
i've practiced more than 100 problems now on backtracking...but still i couldnt solve even an easy leetcode on my own :( dont know why god gave me such low IQ
for some reason leetcode does not like .copy()
I guess you could brute force it by writing your own copy logic. Simplest way would be a list comprehension.
@@spacetoast7783 `list1[:]` is fastest.