【Leetcode 每日一题】131. 分割回文串

问题背景

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

数据约束

• $1\le s.length\le 16$
• $s$ 仅由小写英文字母组成

解题过程

经典回溯题，将分割的过程看作选择在字符之间的哪个位置添加分隔符。

具体实现

选或不选

class Solution {
    private final List<List<String>> res = new ArrayList<>();
    private final List<String> path = new ArrayList<>();
    private String s;

    public List<List<String>> partition(String s) {
        this.s = s;
        dfs(0, 0);
        return res;
    }

    private void dfs(int i, int start) {
        // 当前遍历到的位置已经达到字符串末尾，记录答案并返回
        if (i == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 处理不在当前位置添加分隔符的情况，字符串末尾处是一定要添加的
        if (i < s.length() - 1) {
            dfs(i + 1, start);
        }
        // 在当前位置添加分隔符，判断字串是是否回文
        if (isPalindrome(start, i)) {
            // 添加答案
            path.add(s.substring(start, i + 1));
            // 从下一个位置开始新的递归过程
            dfs(i + 1, i + 1);
            // 恢复现场
            path.remove(path.size() - 1);
        }
    }

    // 判断字符串是否回文，可以当成模板来记
    private boolean isPalindrome(int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

选哪一个

class Solution {
    private final List<List<String>> res = new ArrayList<>();
    private final List<String> path = new ArrayList<>();
    private String s;

    public List<List<String>> partition(String s) {
        this.s = s;
        dfs(0);
        return res;
    }

    private void dfs(int i) {
        // 当前遍历到的位置已经达到字符串末尾，记录答案并返回
        if (i == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 讨论在当前状态下，后续每个可能添加分隔符的位置
        for (int j = i; j < s.length(); j++) {
            if (isPalindrome(i, j)) {
                // 添加答案
                path.add(s.substring(i, j + 1));
                // 从下一个位置开始新的递归过程
                dfs(j + 1);
                // 恢复现场
                path.remove(path.size() - 1);
            }
        }
    }
    
    // 判断字符串是否回文，可以当成模板来记
    private boolean isPalindrome(int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}