Generate All Palindromic Decompositions Of A String ("Palindrome Partitioning" on Leetcode)

Key Takeaways

LICO dream continues another day another question alright so I have a little secret slash surprise for this video we're not going to learn anything new today we are just going to do something we already know how to do so I've covered a lot of backtracking videos and kind of the thing that I want from this channel is for you to internalize the patterns between these questions many questions will have tiny little like heuristics slash leg tricks you can use to solve that but whenever we're tackling these software engineering questions there's I think 15 key like large buckets that these questions fit into which I like delineate in my how to get a job at Google video although I've never worked at Google but these are just the patterns of these questions today we're going to do a backtracking question that fits right into the pattern of string decomposition and it's going to be approached exactly how we tackle other problems like n-queens decomposition of an IP address and many other backtracking problems I've done we're not going to learn anything new today we're just going to apply what we already know and let's see how we apply that right today's question is generate all palindromic decompositions of a string this sounds very intimidating but it is not intimidating we're gonna get output as a string and we're going to decompose that string break it up chop it into pieces each of those pieces are going to be a palindrome this is a palindrome a single letter is a palindrome and mirrors on itself because it's just a single letter it's basically like a base case single letter palindrome single letters all decompositions all these decompositions take away the commas collapse them back together and there are our original string so I want you to notice in the problem giving a string return all decompositions of that string what do you notice the key terms are in this question return all and anytime it's a problem with dealing with decompositions we are going to be exploring a space of decisions exploring a space of possibilities of ways we could go cutting the string up if we explore all those ways and keep our constraints in mind we will be able to answer this question effectively another thing to keep in mind is array and strings these are kind of inserting interchangeable string is just an abstraction of an array characters just keep this in mind so we literally could decompose an array doing backtracking you can decompose a string the reason I said this is something we already know how to do is because we've already covered questions like this we've already done backtracking questions like this so the approach is not going to be any different we're going to advance through this string try different decompositions make choices backtrack on those choices and collect all possibilities when we reach our goal so now let's look at the approaches as well as the three keys to backtracking for this problem for this problem we have two major choices we have the brute force choice where we can generate all decompositions and what we do is we have all these decompositions some are palindromic some are not palindromic we need to validate every single string in that decomposition to check if it's a palindrome and therefore we only add the palindromic decompositions or answer this is brute force what is the problem with this why is this a problem first off we're going to be doing unnecessary work and generating all of these decompositions and second off if we add a non palindrome to our decomposition we instantly disqualify the answer we're going to follow a search tree of decomposition on a decomposition that cannot even be an answer that is a waste of time and that is not the track that we want to go so the key is we need to direct our recursion and we need to choose paths that will yield us an answer we already know this we know the three keys to recursion that I've covered in other videos the three keys to our backtracking are going to be what is our choice we are going to choose a substring to recurse on we're going to have a pointer we're going to take a snippet of the string so I take a significance is ero so then I take a snippet from index 0 to 1 so then I take a snippet of index 0 to 2 and this is the top of our recursion this is our first choice and then what we do is we're going to recurse into that toys and what we need to do is we need to make Evert shirt every sniff we recurse on must be a palindrome or else we are generating an invalid decomposition we're doing unnecessary work we do not want to follow path on a decomposition a decomposed piece that is not a palindrome every piece must be a palindrome our constraints this is simple this is a formula our constraint is that every snippet must be a palindrome we're going to choose a snippet or curse chooses if it recurs and every one of those snippets must be a palindrome when are we finished number three our goal what is our goal our goal is to decompose the whole string our goal is to get our decomposition points are out of bounds when it is out of bounds and equals the length of the string which is indexed to 1 out of bounds we're going to note we have decomposed the whole string we have expressed a potentiality and we can backtrack and express more potential answers this is the key to backtracking these are the three keys so now let's look at the code for this answer and walk through how it does this and again we are not learning anything new we are seeing the patterns we were seeing how patterns apply to other questions all right so a quick thank you to Alex loom at up the hell only code that is a very interesting name um thank you to him for this code and I just adapted it the code is below in github all I did is reformat it I added a ton of comments so that you can understand this but I'm gonna walk through here on the whiteboard so you can see a walk through as well okay we're just going through the same pattern this is the same format we applied to these backtracking problems we understand our choice we understand our constraints or understand or goal up here we have a driver function our driver function creates our list for all of the valid e compositions and creates a list for the decomposition we are working on at the moment through our recursion we hit the play button on our recursion we go into our recursion and our goal is going to be we want to advance our pointer our builds pointer past the array once we are at the arrays length once it builds pointer is at the arrays length then we know we have a value decomposition because up to the points of the base case we were only adding palindromes what we have in our base case is now a palindromic decomposition every one of our choices was within the constraints when we get through the base case we have stayed within the constraints and we have an answer our goal is what crafts our base case and we know that our answer is going to be valid when we reach that base case what we do is we make a decision we start from our builds pointer to the end of the string we take sniffing sniffing sniffing sniffing cut pieces and we validate each of those pieces is that piece of palindrome I don't have to help her here but you can see it in github it's a simple palindrome validation function we see is the snippet that I took a palindrome if it is added to add it to our progress and continue and continue our recursion with our builds points are now pointing at one after the position of the end of our snippet so now we are going to be able to take our snippet and then move on express all the possibilities move on so this is the key and what we do is when this search is over after we have finished exploring all of our options we are going to return to this stack frame each one of these calls is a policy it is a stack frame that expresses potential once that potential is expressed we return to where we were and we're going to hit this line when we come to this line we remove the snippet we just explored on and we choose another significant for example if I have the string AAV I can choose pain and then what I do is my top-level stack frame has three choices it can choose the string of just a or a a or a a B if I choose just a then now I can recurse and I can choose from the rest of the string and then after all that searching is done I return to this top stack frame and now my next top level choice can be a a that is also a palindrome and then i recurse and then that exploring she finishes I come back upwards my next choice is a a B and what happens is then we go to the bottom aap would not even be a path followed because it is not a palindrome now this is our code this is how we do it this is the same pattern and when I told you at the start of this video we wouldn't learn anything new today we have not learned anything new today we just reapplied what we know we reapplied our three keys our choice constraints and gold choice constraints goal we reapplied how we know to do backtracking to solve this problem within the constraints given we have not learned anything new we reapplied what we know and this is the key this is what I want to get at through this channel through these videos I want us to see the patterns so that we can be flexible in answering these questions so now let's look at the time complexities for this solution okay and now let us consider the worst case time and space complexity let us bound the time and space of this of this operation so what is the worst case the worst case we can have is n repetitions and I forgot to do a key thing a key thing is always defined what n is what are the variables in these functions that you're bounding along and is the length of the string and we have and the repetitions of a single character every single decomposition of this string is going to be palindrome and therefore we are going to be yielded the two to the N minus 1 total decompositions all of them will be answers we are going to spend that time computing all of them because they are all decompositions that consists of only palindromes therefore the upper bound we can put on our time is 2 to the N and we spent in linear time in each of the calls we spend linear time and each of the calls so we do many times 2 to the N that is how we bound our time so the way we bound our space is the worst case space complexity is going to be controlled by our call stack we are using recursion we are going to make at max and death on the call stack and what does that look like and we take a snippet a if we take a simple sip a from the overall stream hey we're going to have a depth of three on the call stack what is n n is three that means we are going to use open space as our string increases linearly in length or space is going to increase in a linear fashion as well constants do not matter you are we worried about tail behavior this is the time and space complexity for this problem and this is how we are going to bound it so if you liked this video hit the like button and subscribe to the channel I want to do videos like this every day I have so many topics to cover I have no idea whether I'm going to be able to do all of them this year because it's just hundreds of questions but I want to try my best to establish these patterns I think I've gotten a solid basis in the backtracking front in terms of problem type but there's so many other problem types to explore and see these patterns in my goal is to establish a pattern you can see in all the property types so you can enter the interview and have all the tools you need to succeed so this is what this is all about [Music]