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”,
Return

[
[“aa”,”b”],
[“a”,”a”,”b”]
]

典型的DFS套路:

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));
            return;
        }
        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);
                sol.remove(sol.size()-1);
            }
        }
    }
    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;
            }
            else{
                start++;
                end--;
            }
        }
        return true;
    }
}
Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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