https://oj.leetcode.com/problems/palindrome-partitioning/

LeetCode_PalindromePartitioning.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by benjamin on 10/20/14.
 */
public class PalindromePartitioning {
  public List<List<String>> partition(String s) {
    boolean[][] dp = new boolean[s.length()][s.length()];
    for (int gap = 0; gap < s.length(); gap++) {
      for (int i = 0; i < s.length() - gap; i++) {
        int j = i + gap;
        if (i == j
            || (j == i + 1 && s.charAt(i) == s.charAt(j))
            || (dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j))) {
          dp[i][j] = true;
        } else {
          dp[i][j] = false;
        }
      }
    }

    List<List<String>> results = new ArrayList<List<String>>();
    helper(s, 0, new ArrayList<String>(), dp, results);
    return results;
  }

  private void helper(String s, int begin, List<String> one, boolean[][] dp, List<List<String>> results) {
    if (begin == s.length()) {
      results.add(new ArrayList<String>(one));
      return;
    }

    for (int end = begin; end < s.length(); end++) {
      if (dp[begin][end]) {
        one.add(s.substring(begin, end + 1));
        helper(s, end + 1, one, dp, results);
        one.remove(one.size() - 1);
      }
    }
  }

  public static void main(String[] args) {
    PalindromePartitioning pp = new PalindromePartitioning();
    for (List<String> result: pp.partition("efe")) {
      System.out.println(Arrays.toString(result.toArray(new String[0])));
    }

  }
}