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.

For example, given?s?=?"aab",
Return

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

public class Solution {
	public List<List<String>> partition(String s) {
		int len = s.length();
		List<List<String>>[] res = new List[len + 1];
		res[0] = new ArrayList<List<String>>();
		res[0].add(new ArrayList<String>());
		boolean[][] pair = new boolean[len][len];
		for (int i = 0; i < s.length(); i++) {
			res[i + 1] = new ArrayList<List<String>>();
			for (int j = 0; j <= i; j++) {
				if (s.charAt(i) == s.charAt(j)
						&& (i - j < 2 || pair[j + 1][i - 1])) {
					pair[j][i] = true;
					for (List<String> r : res[j]) {
						List<String> ri = new ArrayList<String>(r);
						ri.add(s.substring(j, i + 1));
						res[i + 1].add(ri);
					}
				}
			}
		}
		return res[len];
	}

}

?

Palindrome Partitioning

原文：http://hcx2013.iteye.com/blog/2220195