Palindrome Partitioning

Source

• lintcode: Palindrome Partitioning

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

Return all possible palindrome partitioning of s.

Example
Given s = "aab", return:

[
  ["aa","b"],
  ["a","a","b"]
]

Java

public class Solution {
    /**
     * @param s: A string
     * @return: A list of lists of string
     */
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<List<String>>();
        dfs(s, new ArrayList<String>(), result);
        return result;
    }

    public void dfs(String s, List<String> path, List<List<String>> result){
        if(s.length()==0){
            result.add(new ArrayList<String>(path));    
            return;
        }

        for(int i=1; i<=s.length(); i++){
            String sub = s.substring(0, i);
            if(isPalindrome(sub)){
                path.add(sub);
                dfs(s.substring(i), path, result);
                path.remove(path.size()-1);
            }
        }
    }

    public boolean isPalindrome(String s){
        int start=0;
        int end = s.length()-1;

        while(start<end){
            if(s.charAt(start)!=s.charAt(end)){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}