Problem

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]

思路

1. 假设字符串s = "abc"
   1. 划分成"a" 和 "bc", 那么我们检查, 如果"a"是回文串, 那么找到 all possible palindrome partitioning of "bc" , 拼接到 "a" 的 路径中
   2. 同理, 划分成"ab" 和 "c", 也是这样做.
2. 也就是说将一个大问题p的划分成p1, p2. 我们解决了p1(p的前部分) , 把p1的答案传下去给p2, 把p2当成原问题p 来处理.
3. 时间复杂度O(n * 2 ^ n)

    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        if (s == null || s.isEmpty()) return result;

        helper(s, 0, result, new ArrayList<String>());
        return result;
    }

    private void helper(String s, int start, List<List<String>> result, List<String> path) {
        if (start >= s.length()) {
            result.add(new ArrayList<String>(path));
            return;
        }

        for (int i = start + 1; i <= s.length(); i++) {
            if (!isPalindrome(s, start, i - 1)) {
                continue;
            }
            path.add(s.substring(start, i));
            helper(s, i, result, path);
            path.remove(path.size() - 1);
        }
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) return false;
        }

        return true;
    }

优化

• isPalindrome() 时间复杂度为 O(n)
• 把检测s所有子串的工作方外递归外面, 将结果存在一个数组里面isPalindrome[start][end]

        boolean[][] dp = new boolean[s.length()][s.length()];
        for(int i = 0; i < s.length(); i++) {
            for(int j = 0; j <= i; j++) {
                if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])) {
                    dp[j][i] = true;
                }
            }
        }