Lexi's Leetcode solutions

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

Posted on: August 3, 2013

这应该是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;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog Stats

  • 222,235 hits
August 2013
M T W T F S S
 1234
567891011
12131415161718
19202122232425
262728293031  
%d bloggers like this: