Leetcode: Palindrome partitioning
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
Example
s = aab
Step 1
prefix = [], remainder = [a,a,b]
Step 2a
prefix = [a], remainder = [a,b]
Step 3a
prefix = [a,a], remainder = [b]
Step 4a
prefix = [a,a,b] remainder = []
Now we can return to step 2a and add one more character and check for palindrome.
Step 2b
prefix = [aa], remainder = [b]
Step 3b
prefix = [aa,b], remainder = []
Step2c
[aab] is not a palindrome and gets discarded.
Solution
The following code snippet shows the recursive implementation.from typing import List, Optional
class Solution:
def partition(self, s: str) -> List[List[str]]:
# Convert string to list of characters
s = [c for c in s]
# Initialize output array/list.
out = []
def inner(prefix, s):
if len(s) == 0:
out.append(prefix)
return
for j in range(1, len(s)+1):
tmp = s[:j]
if tmp == tmp[::-1]:
inner(prefix + ["".join(tmp)], s[j:])
# Call to recursive method
inner([],s)
return out
if __name__ == '__main__':
s = Solution().partition
# print(s('aab'), [['a','a','b'], ['aa', 'b']])
print(s('abacccac'), [
['a','b','a','c','c','c','a','c'],
['aba', 'c', 'c','c','a','c'],
])
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.