pal.java

public class Solution {
	public ArrayList <ArrayList<String>> partition(String s) {
		ArrayList <ArrayList<String>> ret = new ArrayList <ArrayList<String>>();

		if (s == null || s=="")
			return ret;

		ArrayList<String> palindrome = new ArrayList<String>();
		addPalindrome(s, 0, palindrome, ret);

		return ret;
	}
	public void addPalindrome(String s, int start, ArrayList<String> p,
			ArrayList <ArrayList<String>> ret) {
		int e = s.length();
		if (start == e) {
			ArrayList <String> temp = new ArrayList<String>(p);
			ret.add(temp);
			return;
		}
		for (int i = start + 1; i <= e; i++) {
			String str = s.substring(start, i);
			if (isPalindrome(str)) {
				p.add(str);
				addPalindrome(s, i, p, ret);
				//if comment this, fun
				p.remove(p.size() - 1);
			}
		}
	}

	public boolean isPalindrome(String s) {
		int i = 0;
		int e = s.length() - 1;
		while (i < e) {
			if(s.charAt(i++) != s.charAt(e--))
				return false;
		}
		return true;
	}
}