131. Palindrome Partitioning
Medium
Given a string s
, partition s
such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s
.
A palindrome string is a string that reads the same backward as forward.
Example 1:
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Example 2:
Input: s = "a"
Output: [["a"]]
Constraints:
1 <= s.length <= 16
s
contains only lowercase English letters.
class Solution:
def partition(self, s: str) -> List[List[str]]:
result = []
self.dfs(s, 0, result, [])
return result
def dfs(self,string, start= 0, result = [], l = []):
if start >= len(string):
result.append(l[:])
for index in range(start, len(string)):
if self.plaindrome(string[start:index+1]):
l.append(string[start:index+1])
self.dfs(string, index+1, result, l)
l.pop()
def plaindrome(self, string):
return string == string[::-1]
Last updated