LintCode 136 / LeetCode 131 Palindrome Partitioning

思路

dfs搜索。具体思路和组合型dfs模板几乎一致，然后每次搜索到一个新字符串时先判断是否为回文串；这里给出未优化版本和优化版本。
优化1:可以对回文串检测预处理一下，现将所有可能的回文串结果保存到一个isPalindrome数组里，然后检测的时候就可以直接调用了，这里使用动态规划（区间型）的方式进行处理；
优化2:在将合理的答案加入list时，不是直接截取子串然后放入list，而是先将子串结尾下标放入一个list中，最后统一加入result的list中，然后再加入results中。

复杂度

未优化版：
时间复杂度$O(n^2?2^n)$
空间复杂度$O(n)$

优化版：
时间复杂度$O(n?2^n)$
空间复杂度$O(n^2)$

代码

未优化版

class Solution {
    public List<List<String>> partition(String s) {
    List<List<String>> results = new ArrayList<>();if (s == null || s.length() == 0) {
    return results;}dfs(s, 0, new ArrayList<>(), results);return results;}private void dfs(String s,int startIndex,List<String> local,List<List<String>> results) {
    if (startIndex == s.length()) {
    results.add(new ArrayList<>(local));return;}for (int i = startIndex; i < s.length(); i++) {
    String t = s.substring(startIndex, i + 1);if (!isPalindrome(t)) {
    continue;}local.add(t);dfs(s, i + 1, local, results);local.remove(local.size() - 1);}}private boolean isPalindrome(String s) {
    int l = 0, r = s.length() - 1;while (l < r) {
    if (s.charAt(l) != s.charAt(r)) {
    return false;}l++;r--;}return true;}
}

优化版

public class Solution {
    /** @param s: A string* @return: A list of lists of string*/public List<List<String>> partition(String s) {
    // write your code hereList<List<String>> results = new ArrayList<>();if (s == null || s.length() == 0) {
    return results;}boolean[][] isPalindrome = getPalindrome(s);dfs(s, 0, isPalindrome, new ArrayList<>(), results);return results;}private void dfs(String s, int startIndex, boolean[][] isPalindrome,List<Integer> local, List<List<String>> results) {
    if (startIndex == s.length()) {
    addResult(s, local, results);return;}for (int i = startIndex; i < s.length(); i++) {
    if (!isPalindrome[startIndex][i]) {
    continue;}local.add(i);dfs(s, i + 1, isPalindrome, local, results);local.remove(local.size() - 1);}}private void addResult(String s, List<Integer> local, List<List<String>> results) {
    int startIndex = 0;List<String> result = new ArrayList<>();for (int index : local) {
    result.add(s.substring(startIndex, index + 1));startIndex = index + 1;}results.add(result);}private boolean[][] getPalindrome(String s) {
    int len = s.length();boolean[][] isPalindrome = new boolean[len][len];for (int i = 0; i < len; i++) {
    isPalindrome[i][i] = true;}for (int i = 0; i < len - 1; i++) {
    isPalindrome[i][i + 1] = s.charAt(i) == s.charAt(i + 1);}// 第一层循环：长度// 第二层循环：起点，然后可以计算终点for (int length = 3; length <= len; length++) {
    for (int i = 0; i <= len - length; i++) {
    int j = i + length - 1;isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j);}}return isPalindrome;}
}