Friedrich Ewald My Personal Website

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
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

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.

About the author

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.

Related Posts