---
title: 131. Palindrome Partitioning
tags: String
description: share source code.
---

# 131. Palindrome Partitioning

class Solution {
    public List<List<String>> partition(String s) {
     
        int n = s.length();
        
        boolean dp [][] = new boolean [n + 1][n + 1];
        
        List<List<String>> ans = new ArrayList<>();
  
        helper(s, 0, dp , new ArrayList<>(), ans);
      
       return ans;
    }
    
    public void helper(String s, int start, boolean dp [][], List<String> choose, List<List<String>> ans){
        int n = s.length();
        if(start >= n){
            ans.add(new ArrayList<>(choose));
            return;
        }
            
        
        for(int end = start; end < n; end ++){
             if(s.charAt(start) == s.charAt(end) &&  (end - start <= 1 || dp[start + 1][end - 1])){
                dp [start][end] = true;
                choose.add(s.substring(start, end + 1));
                helper(s, end + 1, dp, choose, ans);
                choose.remove(choose.size() - 1);
            }
          }
        }
    
}