131. Palindrome Partitioning
Medium LeetCodeGiven a string s
, partition s
such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s
.
Example 1
Input: s = "
aab
"Output: [["a","a","b"],["aa","b"]]
Explanation: The string "
aab
" can be partitioned as ["a","a","b"] where each substring is a palindrome, or as ["aa","b"] where "aa" is a palindrome and "b" is a palindrome.
Example 2
Input: s = "
a
"Output: [["a"]]
Explanation: The single character "
a
" is already a palindrome, so the only partition is ["a"].
Constraints
1 <= s.length <= 16
s
contains only lowercase English letters
How to solve the problem
- Backtracking (DFS)
python
class Solution:
def partition(self, s: str) -> List[List[str]]:
result = [] # To store all possible palindrome partitioning solutions
path = [] # To store the current single partitioning solution
n = len(s)
# Helper function: checks if a string is a palindrome
def is_palindrome(sub: str) -> bool:
return sub == sub[::-1]
# Depth-First Search (Backtracking) function
def dfs(start_index: int):
# Base case: if the start index reaches the end of the string,
# it means we have found a valid complete palindrome partition.
if start_index == n:
# Add a copy of the current path to the result
result.append(path.copy())
return
# From the start_index, try all possible partition points
for i in range(start_index, n):
# Get the substring
substring = s[start_index : i + 1]
# Check if the substring is a palindrome
if is_palindrome(substring):
# If it's a palindrome, add it to the current path
path.append(substring)
# Continue the DFS on the rest of the string
dfs(i + 1)
# Backtrack: undo the choice to explore other possible partitions
path.pop()
# Start the DFS from index 0
dfs(0)
return result
Complexity
- Time complexity: O(K*C(n, k))
- Space complexity: O(K*C(n, k))
Comments
No comments yet. Be the first to comment!