131 分割回文串

一、题目

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

二、题解

思路：回溯法 + 双指针

对于字符串 s，我们需要把它切分成若干个子串。我们可以把寻找切割点的过程想象成在做选择：

  1. 切割选择： 假设我们当前在处理字符串从索引 startIndex 开始的部分。我们可以选择在 startIndex 之后的任何一个位置 i 砍一刀，切出一个前缀子串 s[startIndex...i]。
  2. 回文校验： 只有当切出来的这个前缀 s[startIndex...i] 是回文串时，这个切割才是有意义的，我们才继续往下走。如果不是回文串，这条分支就可以直接剪枝（放弃）。对于回文串的校验，我们可以很方便地使用双指针（一个指向头，一个指向尾，向中间靠拢）来完成。
  3. 递归与回溯： 如果当前前缀是回文串，我们就把它加入到当前的路径（path）中，然后递归地去处理剩下的字符串（即从 i + 1 开始的部分）。当递归返回后，我们需要“撤销”刚才的切割（把最后加入的子串从 path 中移除），以便去尝试下一种切割可能。
  4. 终止条件： 当我们的切割起点 startIndex 已经越过了字符串的末尾（startIndex >= s.length()），说明整个字符串已经被成功地分割成了若干个回文串，此时把当前的 path 加入到最终的结果集中即可。
import java.util.ArrayList;
import java.util.List;

class Solution {
    List<List<String>> result = new ArrayList<>(); // 存放所有合法分割方案
    List<String> path = new ArrayList<>();         // 存放当前搜索路径上的回文子串

    public List<List<String>> partition(String s) {
        backtrack(s, 0);
        return result;
    }

    private void backtrack(String s, int startIndex) {
        // 终止条件：如果起始位置已经到达或超过字符串末尾，说明找到了一组合法分割
        if (startIndex >= s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }

        // i 代表当前尝试切割的结束位置
        for (int i = startIndex; i < s.length(); i++) {
            // 校验 s[startIndex...i] 是否为回文串
            if (isPalindrome(s, startIndex, i)) {
                // 如果是回文串，截取下来并加入路径
                path.add(s.substring(startIndex, i + 1));

                // 递归：从当前切割点的下一个位置继续往后寻找切割点
                backtrack(s, i + 1);

                // 回溯：撤销刚才的切割，尝试在下一个 i 的位置切割
                path.remove(path.size() - 1);
            } else {
                // 如果不是回文串，直接跳过当前这种切割尝试（隐式剪枝）
                continue;
            }
        }
    }

    // 辅助方法：使用双指针判断子串 s[left...right] 是否为回文串
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

时间复杂度：O(n⋅2n)O(n \cdot 2^n)

空间复杂度：O(n)O(n)

评论