LC131 - Palindrome Partitioning

Problem

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example

Input: s = "aab"

Output: [["a","a","b"],["aa","b"]]

Solution

Use an array to cache palindromity of substring. Time and space complexity is $O(n^2)$.

def partition(self, s: str) -> List[List[str]]:
	arr = [[False] * len(s) for _ in range(len(s))]
	for i in range(len(s)):
		arr[i][i] = True

	for length in range(2, len(s) + 1):	
		for i in range(len(s) - length + 1):
			j = i + length - 1
			if s[i] == s[j]:
				if length == 2 or arr[i + 1][j - 1]:
					arr[i][j] = True
	
	def dfs(start, part):
		if start == len(s):
			res.append(part[:])
			return
	
		for end in range(start, len(s)):
			if arr[start][end]:
	
				dfs(end + 1, part + [s[start:end+1]])
	
	res = []
	dfs(0, [])
	
	return res