Leetcode 131: 分割回文串

题目描述

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。

示例

输入: "aab"
输出:
[
    ["aa","b"],
    ["a","a","b"]
]

思路

思路1： 回溯+判断

即利用回溯思路不断增加是回文前缀字符串组的后续可能回文串

思路1：代码

class Solution {
    public List> partition(String s) {
        List> result = new LinkedList<>();
        if (s.length() == 0) {
            return result;
        }
        List temp = new LinkedList<>();
        partitionHelper(result, s, 0, temp);
        return result;
    }
    
    private boolean canReverse(String s, int i, int j) {
        if (i >= j) {
            return true;
        }
        if (s.charAt(i++) == s.charAt(j--)) {
            return canReverse(s, i, j);
        } else {
            return false;
        }
    }
    
    private void partitionHelper(List> res, String s, int startIndex, List temp) {
        int size = s.length();
        if (size <= startIndex) {
            res.add(new LinkedList(temp));
            return;
        }
        for(int i = startIndex; i < size; i++) {
            if (canReverse(s, startIndex, i)) {
                temp.add(s.substring(startIndex, i + 1));
                partitionHelper(res, s, i + 1, temp);
                temp.remove(temp.size() - 1);
            }
        }
    }
}

思路2：回溯+动态规划优化

空间换时间，将判断是否是回文看成是一个动态规划，直接使用$n^2$算法求取，之后直接$1$调取

思路2: 代码

public class Solution {
    public List> partition(String s) {
        List> res = new LinkedList>();
        if (s.length() == 0) {
            return res;
        }
        int size = s.length();
        boolean[][] dps = new boolean[size][size];
        for(int right = 0; right < size; right++) {
            for(int left = 0; left <= right; left++) {
                if (s.charAt(left) == s.charAt(right) && (right - left <= 2 || dps[left + 1][right - 1])) {
                    dps[left][right] = true;
                }
            }
        }

        List temp = new LinkedList<>();
        partitionHelper(res, s, 0, temp, dps);
        return res;
    }

    private void partitionHelper(List> res, String s, int startIndex, List temp, boolean[][] dps) {
        int size = s.length();
        if (startIndex >= size) {
            res.add(new LinkedList<>(temp));
            return;
        }
        for(int i = startIndex; i < size; i++) {
            if (dps[startIndex][i]) {
                temp.add(s.substring(startIndex, i + 1));
                partitionHelper(res, s, i + 1, temp, dps);
                temp.remove(temp.size() - 1);
            }
        }
    }
}

复杂度分析

思路1

时间复杂度

$n*2^n?$

空间复杂度

$n*2^n?$

思路2

时间复杂度

$2^n + n^2$

空间复杂度

$n * 2^n + n^2$