#77 Medium Time O(n·2^n) Space O(n) Animated

Palindrome Partitioning

Partition a string such that every substring is a palindrome.

LeetCode ↗

Approach: DFS (Backtracking)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

Partition a string such that every substring is a palindrome.

Constraints

Time Complexity: O(n·2^n)
Space Complexity: O(n)

Solution — DFS (Backtracking)

O(n·2^n) O(n)

def partition(s):
    res = []
    part = []
    
    def dfs(i):
        if i >= len(s):
            res.append(part.copy())
            return
        for j in range(i, len(s)):
            if self.isPali(s, i, j):
                part.append(s[i:j+1])
                dfs(j + 1)
                part.pop()
                
    dfs(0)
    return res
    
def isPali(self, s, l, r):
    while l < r:
        if s[l] != s[r]: return False
        l, r = l + 1, r - 1
    return True

Word Search

Letter Combinations of a Phone Number

Palindrome Partitioning

Steps

Description

Constraints

Tags

Solution — DFS (Backtracking)