[leetcode] Palindrome Partitioning | 分解string使每个substring都中心对称，返回所有分解可能。

Posted by: lexigrey on: August 3, 2013

• In: leetcode
• Leave a Comment

这应该是DFS，和CC上那道题也很像，但是实在是做不出来。。而且用binary分解那种方法想出来了，但是时间复杂度也弄不明白。崩溃了。这样下去，周一的MS会挂把。。。

———————–两个月之后———————-

一次Bugfree。看来人真是会成长的。。和word break一样做，abaa先分成a, baa，然后再分成ab, aa，左边是palindrome才recurse on右边：

public ArrayList<ArrayList<String>> partition(String s) {
  Map<String, ArrayList<ArrayList<String>>> cache = new HashMap<String, ArrayList<ArrayList<String>>>();
  return partition(s, cache);
}
private ArrayList<ArrayList<String>> partition(String s, Map<String, ArrayList<ArrayList<String>>> cache) {
  if (cache.containsKey(s))
    return cache.get(s);
  ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
  if (s.isEmpty()) {
    result.add(new ArrayList<String>());
  }
  for (int i = 0; i < s.length(); i++) {
    String left = s.substring(0, i + 1);
    if (isPalindrom(left)) {
      String right = s.substring(i + 1);// right maybe empty
      ArrayList<ArrayList<String>> rightPartitions = partition(right);
      for (ArrayList<String> rightPartition : rightPartitions) {
        rightPartition.add(0, left);
        result.add(rightPartition);
      }
    }
  }
  cache.put(s, result);
  return cache.get(s);
}
private boolean isPalindrom(String left) {
  for (int i = 0; i < left.length() / 2; i++) {
    if (left.charAt(i) != left.charAt(left.length() - 1 - i))
      return false;
  }
  return true;
}

Tags: dfs, string, 固定解法