1
// Plaindrome Partitioning
2
// Leetcode : https://leetcode.com/problems/palindrome-partitioning/
3

4
class Solution {
5
  public List<List<String>> partition(String s) {
6
    List<List<String>> result = new ArrayList<>();
7
    if (s == null || s.length() == 0) return result;
8
    helper(s, 0, new ArrayList<String>(), result);
9
    return result;
10
  }
11

12
  private void helper(String s, int start, List<String> list, List<List<String>> result) {
13
    if (start == s.length()) {
14
      result.add(new ArrayList<>(list));
15
      return;
16
    }
17
    for (int i = start; i < s.length(); i++) {
18
      if (isPalindrome(s, start, i)) {
19
        list.add(s.substring(start, i + 1));
20
        helper(s, i + 1, list, result);
21
        list.remove(list.size() - 1);
22
      }
23
    }
24
  }
25

26
  private boolean isPalindrome(String s, int start, int end) {
27
    while (start < end) {
28
      if (s.charAt(start++) != s.charAt(end--)) return false;
29
    }
30
    return true;
31
  }
32
}