LeetCode 解题思路 31（Hot 100）

解题思路：

1. 递归参数： 字符串 s、结果集 result、当前路径 path、回文子串数组 dp、开始位置 start。
2. 递归过程：

• 当当前路径 path 的长度等于 s.length() 时，说明已经分割完成，加入结果集。
• 若当前起止位置满足回文条件，将当前子串加入 path，递归处理字符串的下一个位置。
• 递归返回后，撤销选择（回溯），继续尝试其他可能的分割方式。

Java代码：

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        List<String> path = new ArrayList<>();
        boolean[][] dp = isPalindrome(s);
        
        backtrack(s, result, path, dp, 0);
        return result;
    }

    private boolean[][] isPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 1) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
            }
        }
        return dp;
    }

    private void backtrack(String s, List<List<String>> result, List<String> path, boolean[][] dp, int start) {
        if (start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int end = start; end < s.length(); end++) {
            if (dp[start][end]) { 
                path.add(s.substring(start, end + 1));
                backtrack(s, result, path, dp, end + 1);
                path.removeLast();
            }
        }
    }
}

复杂度分析：

• 时间复杂度： 预处理 O($n^2$)，回溯 O($n{2}^n$) → 总时间复杂度仍为 O($n2+n{2}^n$)。
• 空间复杂度： O($n^2$)。

解题思路：

1. 递归参数： 皇后个数 n、结果集 result、当前棋盘 chessboard、开始行数 row。
2. 递归过程：

• 当当前行数 row 的大小等于 n 时，说明棋盘填充完成，加入结果集。
• 若当前行的第 col 个位置满足填充条件，将当前位置填充 Q，递归处理下一行。
• 递归返回后，撤销选择（回溯），继续尝试其他可能的填充方式。

3. 辅助函数：

• public List Array2List(char[][] chessboard)：将当前二维字符数组 chessboard 转换成符合结果的 List。
• public boolean isValid(int n, char[][] chessboard, int row, int col)：判断当前位置是否满足皇后规则。

Java代码：

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) Arrays.fill(c, '.');
        backtrack(n, result, chessboard, 0);
        return result;
    }


    public void backtrack(int n, List<List<String>> result, char[][] chessboard, int row) {
        if (row == n) {
            result.add(Array2List(chessboard));
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isValid (n, chessboard, row, col)) {
                chessboard[row][col] = 'Q';
                backtrack(n, result, chessboard, row + 1);
                chessboard[row][col] = '.';
            }
        }

    }


    public List Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();
        for (char[] c : chessboard) list.add(String.copyValueOf(c));
        return list;
    }


    public boolean isValid(int n, char[][] chessboard, int row, int col) {
        for (int i = 0; i < row; i++) { 
            if (chessboard[i][col] == 'Q') return false;
        }

        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') return false;
        }

        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
            if (chessboard[i][j] == 'Q') return false;
        }

        return true;
    }
}

复杂度分析：

• 时间复杂度： 最坏情况下为 O(n!)。
• 空间复杂度： O(n)。