LeetCode 131. 分割回文串

131. 分割回文串

解题思路

选择在哪个位置进行分割 决策树
从字符串的下表 0 开始尝试分割
枚举分割点: s[index, i] 和 s[i + 1, s.length() - 1]
剪枝: s[index, i] 不是回文串，跳过这个分割点
递归 回溯 终止

维护 dp 数组，记录子串 s[i][j] 是否为回文串

参考代码

class Solution {
    private List<List<String>> result = new ArrayList<>();
    private List<String> tmp = new ArrayList<>();

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

    private void dfs(String s, int index) {
        // 终止条件
        if(index == s.length()) {
            result.add(new ArrayList(tmp));
            return;
        }

        for(int i = index; i < s.length(); i ++) {
            if(!isHW(s, index, i)) {
                continue;
            }
            tmp.add(s.substring(index, i + 1));
            dfs(s, i + 1);
            tmp.remove(tmp.size() - 1);
        }
    }

    private boolean isHW(String s, int left, int right) {
        while(left < right) {
            if(s.charAt(left) != s.charAt(right)) {
                return false;
            } else {
                left ++;
                right --;
            }
        }
        return true;
    }
}

空间换时间

class Solution {
    private List<List<String>> result = new ArrayList<>();
    private List<String> tmp = new ArrayList<>();
    // 记录字符串 s 中从索引 i 到 j 的子串是否是回文串
    private boolean[][] dp;

    public List<List<String>> partition(String s) {
        dp = new boolean[s.length()][s.length()];
        dfs(s, 0, dp);
        return result;
    }

    private void dfs(String s, int index, boolean[][] dp) {
        // 终止条件
        if(index == s.length()) {
            result.add(new ArrayList(tmp));
            return;
        }

        for(int i = index; i < s.length(); i ++) {
            if(!isHW(s, index, i, dp)) {
                continue;
            }
            tmp.add(s.substring(index, i + 1));
            dfs(s, i + 1, dp);
            tmp.remove(tmp.size() - 1);
        }
    }

    /**
     * 判断是否是回文串
     */
    private boolean isHW(String s, int left, int right, boolean[][] dp) {
        if(dp[left][right]) return true;

        while(left < right) {
            if(s.charAt(left) != s.charAt(right)) {
                dp[left][right] = false;
                return false;
            } else {
                left ++;
                right --;
            }
        }
        dp[left][right] = true;
        return true;
    }
}