Welcome to my personal website. I use this space to share some of my thoughts and software that I write in my free time. Sometimes I also publish photos. If you want to get in touch please use LinkedIn or Mastodon.
Given a string s, return a list containing of all possible partitions of that string that are palindromes. A palindrome is a string that is the same backwards as forwards. For example, abba is a palindrome.
The string aab can be partitioned as follows: [['a','a','b'], ['aa','b']]. This is because a single character is by definition a palindrome.
When thinking about the solution, we need to first think about the cases. The palindrome can be
at the beginning,
in the middle,
or at the end
of the string. Additionally there can be more than one palindrome at the same time. The base case is that every character is a palindrome on its own.
One possible solution is to look at this as a recursive problem with a prefix and a remainder of the string. We can then attempt to greedily find palindromes in the remainder.
Example
Solution
The following code snippet shows the recursive implementation.
Runtime: 1690 ms, faster than 5.03% of Python3 online submissions for Palindrome Partitioning. Memory Usage: 30.4 MB, less than 45.23% of Python3 online submissions for Palindrome Partitioning.
About the author
Friedrich Ewald is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.