Problem: 131. 分割回文串

题目描述

思路

题目要求我们给出所有的回文子字符串，而涉及到穷举我们可以利用回溯来解决，另外我们也可以发现问题中涉及到元素存在重复但不可复用的特性，因此我们可以类似于利用回溯求解组合问题的套路求解，具体的：

我们以字符串中的每一个字符作为决策阶段，在回溯调用的过程中，每次进行回文判断，若判断当前决策路径上的子字符串为回文字符串，则将其添加到决策路径，并最终当决策阶段等于字符串的长度时将决策路径添加到结果集合中

解题方法

1.定义二维结果集result，决策路径path
2.编写判断回文字符串函数
3.编写调用回溯函数，初始决策阶段为0

3.1 若当前的决策路径等于字符串的长度，则将当前的决策路径添加到结果集result中并返回
3.2 for循环，令循环初始位置i等于当前的决策阶段（假设为k），并判断，若i到k位置的子字符串为回文串则将其添加到当前的决策路径，并开始下一阶段的递归调用，最后恢复当前决策路径的状态

复杂度

时间复杂度:

最坏时间复杂度： $O(n\times 2^n)$

空间复杂度:

递归开辟的栈空间 $O(2^n)$

Code

class Solution {
    //Result list
    List<List<String>> result = new ArrayList<>();
    //Decision Path
    List<String> path = new ArrayList<>();

    /**
     * Gets all return substrings
     *
     * @param s Given string
     * @return List<List < String>>
     */
    public List<List<String>> partition(String s) {
        backtrack(s, 0);
        return result;
    }

    /**
     * Get all backtrace substrings using backtrace
     *
     * @param s Given string
     * @param k Decision stage
     */
    public void backtrack(String s, int k) {
        //End condition
        if (k == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int end = k; end < s.length(); ++end) {
            //
            if (isPalindrome(s, k, end)) {
                path.add(s.substring(k, end + 1));
                backtrack(s, end + 1);
                //Recover the current Decision Path
                path.remove(path.size() - 1);
            }
        }
    }

    /**
     * Determines whether a string is a palindrome string
     *
     * @param s     Given string
     * @param start The start position of given string
     * @param end   The end position of given string
     * @return boolean
     */
    private boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}