MediumNo. 0131
Palindrome Partitioning — LeetCode 131 Python Solution
- Pattern
- Backtracking
- Topics
- String, Dynamic Programming, Backtracking
- On a study list
- NeetCode 150
- Reading time
- 4 min
- Source
- leetcode.com
The 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"]]
Python solution
class Solution:
def partition(self, s: str) -> List[List[str]]:
def dfs(i: int):
if i == n:
ans.append(t[:])
return
for j in range(i, n):
if f[i][j]:
t.append(s[i : j + 1])
dfs(j + 1)
t.pop()
n = len(s)
f = [[True] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
f[i][j] = s[i] == s[j] and f[i + 1][j - 1]
ans = []
t = []
dfs(0)
return ansComplexity
- Time
- O(n × 2n)
- Space · auxiliary
- O(n2)
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 131. Palindrome Partitioning is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0132 | Palindrome Partitioning II | Hard |
| 1278 | Palindrome Partitioning III | Hard |
| 1745 | Palindrome Partitioning IV | Hard |
| 0022 | Generate Parentheses | Medium |
| 2002 | Maximum Product of the Length of Two Palindromic Subsequences | Medium |
| 0010 | Regular Expression Matching | Hard |
Frequently asked questions
- How hard is LeetCode 131. Palindrome Partitioning?
LeetCode 131. Palindrome Partitioning is rated Medium on LeetCode.
- What is the time complexity of LeetCode 131. Palindrome Partitioning?
The Python solution on this page runs in O(n × 2n).
- What is the space complexity of LeetCode 131. Palindrome Partitioning?
The Python solution on this page uses O(n2) auxiliary space.
- What topics does LeetCode 131. Palindrome Partitioning cover?
LeetCode 131. Palindrome Partitioning is tagged String, Dynamic Programming and Backtracking on LeetCode.