[Leetcode] 131. Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/description/?envType=company&envId=facebook&favoriteSlug=facebook-six-months

initial

i didnt know

u have to partition the stirng into substrings

sol

so for backtracking's parameters, i put start+1 and path into the next recursion. But i should have put i+1 where i is the ending point.

start is where you begin looking
i is where you end the current substring
Next recursion should start after where you ended, not after where you started

When you cut s[0:2]="aa", next position should be index 2 (after "aa"), not index 1 (start+1).

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []
        current = []
        
        def isPalindrome(string):
            return string == string[::-1]
        
        def backtrack(start):
            # Base case: reached end of string
            if start == len(s):
                result.append(current[:])  # Make a copy
                return
            
            # Try all possible cuts from start position
            for end in range(start, len(s)):
                substring = s[start:end+1]
                
                # If current substring is palindrome
                if isPalindrome(substring):
                    current.append(substring)  # Choose
                    backtrack(end + 1)          # Explore
                    current.pop()               # Unchoose (backtrack)
        
        backtrack(0)
        return result

How it works:

For s = "aab":

backtrack(0):
  Try s[0:1]="a" ✓ palindrome
    current=["a"]
    backtrack(1):
      Try s[1:2]="a" ✓ palindrome
        current=["a","a"]
        backtrack(2):
          Try s[2:3]="b" ✓ palindrome
            current=["a","a","b"]
            backtrack(3): ✓ FOUND! Add ["a","a","b"]
      Try s[1:3]="ab" ✗ not palindrome, skip
  
  Try s[0:2]="aa" ✓ palindrome
    current=["aa"]
    backtrack(2):
      Try s[2:3]="b" ✓ palindrome
        current=["aa","b"]
        backtrack(3): ✓ FOUND! Add ["aa","b"]
  
  Try s[0:3]="aab" ✗ not palindrome, skip

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        ans = []
        def isPalin(input_string):
            if input_string==input_string[::-1]:
                return True
            return False
        def dfs(path,start):
            nonlocal ans
            if start==len(s):
                ans.append(path.copy())
            for i in range(start,len(s)):
                if isPalin(s[start:i+1]):
                    path.append(s[start:i+1])
                    dfs(path,i+1)
                    path.pop()
        dfs([],0)
        return ans

revisited java dec 2025

initial
1) dfs is already partitioning so this main for loop is unnecessary

for(int i=0; i<s.length(); i++){
    List<String> temp = new ArrayList<>();
    dfs(i, temp, s, ans); // This is the problem
}

2) i recurred even when the current substring isnt a palindrome

if(isPalindrome(string_so_far)) {
    temp.add(string_so_far);
    dfs(i + 1, temp, s, ans);
    temp.remove(temp.size() - 1);
} else {
    // What happens here?
    dfs(i + 1, temp, s, ans); // Potential issue
}

thats wrong cuz we only want palindrome substrings in current recursion branch. if current substring isnt one, we should stop recurring immediately

complexity

at each position, we choose whether to partition or not so it is 2^n. for each partition, we also check if its palindrome and reversing string takes n time.

so total time is n * 2^n and n space