A week of LeetCode (day 6/7)
Welcome to our technical interview preparation series for the sixth time. Our goal is to pave the way for you to land your dream job with ease by providing you with real problem-solving skills covering lots of topics.
Don’t forget to check the previous articles:
- Day (1/15): Basic arithmetic
- Day (2/15): Two pointers technique
- Day (3/15): Greedy thinking
- Day (4/15): Binary Search + BSGS + PIE
- Day (5/15): Do the math!
- Day (6/15): The Brute-force guy
- Day (7/15): Geometry
Let’s not waste time and jump right in!
A short sad story:
Throughout this series we have almost always represented any brute-force algorithm as a bad guy, with a terrible time complexity, which is often true, so today we counter that idea and show some cases in which the brute-force guy is useful.
Brute force is not a specific algorithm with well-known steps. In fact, it is a way of solving a problem by exhausting all outcomes.
Day 6: Palindrome Partitioning
I will assume you haven’t read the task description, so here is a summary:
Given a string S, partition it into some substrings, such that they cover the whole string, and each substring is palindrome.
Return the set of all valid partitions.
A palindrome string is a string that reads the same backward as forward.
Example:
S = "aab"
First partition: "a", "a" , "b"
Second partition: "aa", "b"
A general rule of thumb is: if the problem constraints are small, you probably should dial the brute-force guy, remember the length of the given string is up to 16, which is pretty small, so here we are calling the guy.
Now let’s see what our guy would do in this situation:
Since the partition must cover the whole string, the first piece of the partition has to be a prefix of it (the given string), so we just try all prefixes.
Now that we have the first piece, let’s denote its length by k, we ignore the first k characters of S and start looking for the second piece from the (k+1)-th character of S, eventually, we will end up with a valid partition that covers all of S.
Let’s try an example to clear any doubts.
S = “aba”
We have 3 choices for the first substring “a”, “ab” or “aba”, however only “a” and “aba” can be used as “ab” isn’t a palindrome.
We take the first option and append “a” to the partition, now S becomes “ba”, recall that we ignore the characters that we have already used.
Then similarly we have two possible prefixes (either “b” or “ba”) but only “b” is a palindrome, again we append it to the partition, so we are left with S = “a”, we no longer have choices but to append it to the partition, and by now we have the first partition [“a”, “b”, “a”].
Now let’s jump back to the first choice we made, and choose the “aba” to be the first piece instead of “a”, so we have our second partition [“aba”].
Pseudo-code:
bruteforce(S, cur_partition)
answer = 0
n = length(S) if S is empty
append the partition to the list of answers
return try all possible prefixes p_1, p_2,... ,p_n
if p_i is palindrome
bruteforce( S[i+1,n], cur_partition + p_i )
return answer
That is all we need, let's write some code!
C++ Implementation
Python Implementation
What to learn from the brute-force guy?
- Break the problem in your hand into smaller sub-problems: this technique is very useful, as smaller problems tend to have simpler and sometimes well-known solutions.
- Think about how to solve the smaller sub-problems efficiently and combine them into one final happy solution.
- Exhausting all possible outputs is not bad in practice, given that the constraints are small.
- Reread this article many times until you fully appreciate it.
Your Turn:
Congratulations! If you made it here in one sitting, I knew you could do it.
Now that you hopefully acquired some new skills, especially brute-force, Don’t stop here, put them into practice. Try to be a brute-force guy ;)
Additional Problems for practice:
