< Back




131. Palindrome Partitioning

We're given a string, s, and asked to return all possible partitions of s such that each substring is
a palindrome. Revisiting what a palindrome is, it's a string that reads the same forwards and
backwards.

We use backtracking similar to how we tackled the 93. Restore IP Addresses
problem, except we don't have to maintain the index of dots, we just have to maintain the index of
where we're paritioning the string. What's nice is we also don't have to maintain a remainder
variable to know how many characters are left, because we're just chopping off characters as we
traverse each node in the search.

So we, be default, start of by inspecting partitions where the substrings are length one. Obviously,
these pass the palindrom check, then we add this partition to our path and continue to backtrack on
the remaining characters. During each step, our iteration through the characters becomes smaller as
we remove characters from the start of the string.

Eventually, when we run out of characters, we know that all partitions in our path are palindromes,
so we append them to our answer.

The solution is as follows:


  class Solution:
      def partition(self, s: str) -> List[List[str]]:
          self.ans = []

          def backtrack(t: str, path: List[str]) -> None:
              if not t:
                  self.ans.append(path)
                  return

              for i in range(1, len(t) + 1):
                  if t[:i] == t[:i][::-1]:
                      backtrack(t[i:], path + [t[:i]])

          backtrack(s, [])

          return self.ans


_ Time Complexity:

  O(2^n * n) - Where n is the length of the string.

_ Space Complexity:

  O(n) - Our recursion stack can reach length n.