# Java Backtracking solution beats 100%

• First, build a 2d n*n String array isPalindrome in O(n^2) time, where isPalindrome[i][j] means that s.substring(i, j + 1) is a palindrome.
Then, backtrack starting from index 0 to compute all possible lists of palindromes, adding them to the result when the recursing index reaches the end of the string.

``````public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
if(s == null || s.length() == 0)
return res;
int n = s.length();
String[][] isPalindrome = new String[n][n];
buildSubPalindromes(s, isPalindrome);
backtrack(res, new ArrayList<>(), isPalindrome, 0);
return res;
}

public void backtrack(List<List<String>> res, List<String> curr, String[][] isPalindrome, int idx) {
if(idx == isPalindrome.length) {
return;
}

for(int i = idx; i < isPalindrome.length; ++i) {
if(isPalindrome[idx][i] != null) {
backtrack(res, curr, isPalindrome, i + 1);
curr.remove(curr.size() - 1);
}
}
}

public void buildSubPalindromes(String s, String[][] isPalindrome) {
int n = s.length();
for(int i = 0; i < n; ++i) {
int left = i;
int right = i;
while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
isPalindrome[left][right] = s.substring(left, right + 1);
--left;
++right;
}

left = i - 1;
right = i;
while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
isPalindrome[left][right] = s.substring(left, right + 1);
--left;
++right;
}
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.