🌕 🌗 131. 分割回文串

难度: 🌕 🌗

问题描述

---

解法

class Solution {
    List<List<String>> res = new LinkedList<>();
    public List<List<String>> partition(String s) {
        // 思路：
        // dp 记录任意区间是否是回文串
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        for(int i = len - 1; i >= 0; i --) {
            for(int j = i; j < len; j ++) {
                if(i == j) {
                    dp[i][j] = true;
                } else if(i == j - 1) {
                    if(s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = true;
                    }
                } else {
                    if(s.charAt(i) == s.charAt(j)) {
                        dp[i][j] |= dp[i + 1][j - 1];
                    }
                }
            }
        }
        LinkedList<String> path = new LinkedList<>();
        mySol(s, dp, len, 0, path);
        return res;
    }

    private void mySol(String s, boolean[][] dp, int len, int index, LinkedList<String> path) {
        // 递归终止条件
        if(index >= len) {
            res.add(new LinkedList<>(path));
            return;
        }
        // index <= len
        for(int i = index; i < len; i ++) {
            // 以 i 为右边界，找到满足条件的回文串
            if(dp[index][i]) {
                path.addLast(s.substring(index, i + 1));
                mySol(s, dp, len, i + 1, path);
                path.removeLast();
            }
        }
    }

    private void print(LinkedList<String> path) {
        System.out.println("------------");
        for(int i = 0; i < path.size(); i ++) {
            System.out.print(path.get(i) + " , ");
        }
        System.out.println("------------");
    }
}

---

输出