Palindrome Partitioning

LeetCode Q 131 - 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:
Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ]

Solution : Backtracking

Code:

private List<List<String>> res;

public List<List<String>> partition(String s) {
	res = new ArrayList<>();
	if (s == null || s.length() == 0) return res;
	backtrack(s, new ArrayList<>(), 0);
	return res;
}

private void backtrack(String s, List<String> temp, int index) {
	if (index == s.length()) {
		res.add(new ArrayList(temp)); return;
	}
	
	for (int i = index; i < s.length(); i++) {
		if (isPalindromic(s, index, i)) {
			temp.add(s.substring(index, i + 1));
			backtrack(s, temp, i + 1);
			temp.remove(temp.size() - 1);
		}
	}

	return;
}

private boolean isPalindromic (String s, int left, int right) {
	while (left < right) {
		if (s.charAt(left) != s.charAt(right)) return false;
		left++; right--;
	}
	retur true;
}