2020-05-03 131. Palindrome Parti

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"]]

这题一开始想法是每个字符有两种情况：加到当前字符串，或加到下一个字符串。后来看了下别人的答案，其实直接先判断是否回文，再进行list的add操作，更省时间。

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，这题我完全一样的答案，提交上去有时候4ms，有时候2ms，弄得百分比也不一样，还以为代码还有哪里有问题，结果拷贝了2ms的答案跑出来也要5ms左右