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 n = s.length(); boolean[][] dp = new boolean[n][n]; List<List<String>>[] res = new List[n + 1]; res[0] = new ArrayList<>(); res[0].add(new ArrayList<>()); for (int i = 0; i < n; i++) { res[i + 1] = new ArrayList<>(); for (int j = 0; j <= i; j++) { if (s.charAt(i) == s.charAt(j) && (i - j < 2 || dp[j + 1][i - 1])) { dp[j][i] = true; String t = s.substring(j, i + 1); for (List<String> pre: res[j]) { List<String> cur = new ArrayList<>(pre); cur.add(t); res[i + 1].add(cur); } } } } return res[n]; } }