回文分割

回文分割

问题

这个题目说的是，给你一个字符串，你要把它分割成子串，并且每个子串都是回文串。你要返回所有可能的子串集合。

比如说，给你的字符串是：

aad

它有两种可能的分割方法。一种是分割成 aa 和 d。aa 是回文串，d 作为单个字符也是回文串。

另一种是分割成 a，a 和 d，3 个子串都是单字符的回文串。

代码

public class AlgoCasts {

  private void partition(String s, int start, boolean[][] d,
                         List<List<String>> result, List<String> elem) {
    if (start >= s.length()) {
      result.add(new ArrayList<>(elem));
    } else {
      for (int end = start; end < s.length(); ++end) {
        if (d[start][end]) {
          elem.add(s.substring(start, end+1));
          partition(s, end+1, d, result, elem);
          elem.remove(elem.size()-1); // T: O(1)
        }
      }
    }
  }

  // Time: O(2^n), Space: O(n^2)
  public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();
    if (s == null || s.length() == 0) return result;
    int n = s.length();
    boolean[][] d = new boolean[n][n];

    for (int i = n-1; i >= 0; --i) {
      for (int j = i; j < n; ++j) {
        if (i == j) d[i][j] = true;
        else if (i+1 == j) d[i][j] = s.charAt(i) == s.charAt(j);
        else d[i][j] = s.charAt(i) == s.charAt(j) && d[i+1][j-1];
      }
    }

    partition(s, 0, d, result, new ArrayList<>());
    return result;
  }

}