Palindrome Partitioning, Leetcode 解题笔记

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = “aab”,



public class Solution {
    public ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();
        ArrayList<String> sol = new ArrayList<String>();
        if(s == null || s.length() == 0) return ret;
        dfs(ret, sol, 0, s);
        return ret;
    public void dfs(ArrayList<ArrayList<String>> ret, ArrayList<String> sol, int start, String s){
        if(start == s.length()){
            ret.add(new ArrayList<String>(sol));
        for(int i = start+1; i <= s.length(); i++){
            if(check(s.substring(start, i))){
                sol.add(s.substring(start, i));
                dfs(ret, sol, i, s);
    public boolean check(String s){
        int start = 0;
        int end = s.length()-1;
        while(start < end){
            if(s.charAt(start) != s.charAt(end)){
                return false;
        return true;

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s