131_Palindrome_Partitioning.java

classSolution {
publicList<List<String>> partition(Strings) {
if (s == null || s.length() == 0) {
returnCollections.emptyList();
 }

List<List<String>> result = newArrayList<>();
helper(s, 0, result, newArrayList<>());

returnresult;
 }

privatevoidhelper(Strings, intidx, List<List<String>> result, List<String> temp) {
if (idx == s.length()) {
result.add(newArrayList<>(temp));
return;
 }

for (inti = idx; i < s.length(); i++) {
if (isPalindrome(s, idx, i)) {
temp.add(s.substring(idx, i + 1));
helper(s, i + 1, result, temp);
temp.remove(temp.size() - 1);
 }
 }
 }

privatebooleanisPalindrome(Strings, intleft, intright) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
returnfalse;
 }

 ++left;
 --right;
 }

returntrue;
 }
}