[leetcode] Palindrome Partitioning | 分解string使每个substring都中心对称,返回所有分解可能。
Posted August 3, 2013
on:这应该是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