Palindrome Partitioning — LeetCode 131 Python Solution
MediumStringDynamic ProgrammingBacktracking
- Problem
- #131
- Pattern
- Backtracking
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(n \times 2^n) |
| Space | O(n^2) auxiliary |
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
On a study list
This problem is on NeetCode 150.
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 \times 2^n).
- What is the space complexity of LeetCode 131. Palindrome Partitioning?
- The Python solution on this page uses O(n^2) auxiliary space.
- What topics does LeetCode 131. Palindrome Partitioning cover?
- LeetCode 131. Palindrome Partitioning is tagged String, Dynamic Programming and Backtracking on LeetCode.