# Java solution with preliminary indexation, beats 95%

• Basically the solution is standard recursive forward traversing of the string creating chains of substrings that are palindromes. Although there is lots of repeating work for checking substrings to be palindromes. To remove this caveat we can prepare the two-level matrix `boolean[][] palindromes` of all palindromes in the string that will show answer the question "Is there palindrome in the substring (i, j)?" in linear time.
Indexing is pretty straightforward as well as traversing

``````public List<List<String>> partition(String s) {
boolean[][] palindromes = findAllPalindromes(s);
List<List<String>> result = new ArrayList<>();
partition(s, 0, palindromes, new ArrayList<>(), result);
return result;
}

public boolean[][] findAllPalindromes(String s) {
if (s.length() == 1) {
return new boolean[][]{{true, true}};
}
boolean[][] palindromes = new boolean[s.length()][s.length()];
for (int idx = 0; idx < s.length(); idx++) {
// Case 1: the character is at the center of palindrome
for (int i = idx, p = idx; i >= 0 && p < s.length(); i--, p++) {
if (s.charAt(i) != s.charAt(p))
break;
palindromes[i][p] = true;
}

// Case 2: character is the same as its neighbour
if (idx < s.length() - 1) {
for (int i = idx, p = idx + 1; i >= 0 && p < s.length(); i--, p++) {
if (s.charAt(i) != s.charAt(p))
break;
palindromes[i][p] = true;
}
}
}

return palindromes;
}

public void partition(String s, int idx, boolean[][] p, List<String> current, List<List<String>> result) {
if (idx == s.length()) {