Given a string?s, partition?s?such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of?s.
Example:
Input:"aab"Output:[? ["aa","b"],? ["a","a","b"]]
這題一開始想法是每個(gè)字符有兩種情況：加到當(dāng)前字符串，或加到下一個(gè)字符串。后來看了下別人的答案，其實(shí)直接先判斷是否回文，再進(jìn)行l(wèi)ist的add操作，更省時(shí)間。
class Solution {
? ? public List<List<String>> partition(String s) {
? ? ? ? // System.out.println("input: " + s);
? ? ? ? List<List<String>> res = new LinkedList<>();
? ? ? ? LinkedList<String> cur = new LinkedList<String>();
? ? ? ? backtrace(cur, res, s, 0);
? ? ? ? return res;
? ? }
? ? private void backtrace(LinkedList<String> cur, List<List<String>> res, String s, int index) {
? ? ? ? // System.out.println(String.format("cur: %s, index: %d, s: %s", Arrays.deepToString(cur.toArray()), index, s));
? ? ? ? if (index == s.length()) {
? ? ? ? ? ? res.add(new ArrayList<>(cur));
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? for (int r = index; r < s.length(); r++) {
? ? ? ? ? ? if (isPalindrome(s, index, r)) {
? ? ? ? ? ? ? ? cur.add(s.substring(index, r + 1));
? ? ? ? ? ? ? ? backtrace(cur, res, s, r + 1);
? ? ? ? ? ? ? ? cur.removeLast();
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? private boolean isPalindrome(String s, int l, int r) {
? ? ? ? while (l < r) {
? ? ? ? ? ? if (s.charAt(l) != s.charAt(r)) return false;
? ? ? ? ? ? l++; r--;
? ? ? ? }
? ? ? ? return true;
? ? }
}
還要吐槽leetcode，這題我完全一樣的答案，提交上去有時(shí)候4ms，有時(shí)候2ms，弄得百分比也不一樣，還以為代碼還有哪里有問題，結(jié)果拷貝了2ms的答案跑出來也要5ms左右
