LeetCode 热题 100 之 131. 分割回文串 51. N 皇后

131.分割回文串51.N 皇后131. 分割回文串class Solution { public ListListString partition(String s) { ListListString res new ArrayList(); ListString path new ArrayList(); backtrack(s, 0, path, res); return res; } // start当前要分割的起始位置 private void backtrack(String s, int start, ListString path, ListListString res) { // 终止条件起始位置等于字符串长度说明已完成一次有效分割 if (start s.length()) { res.add(new ArrayList(path)); return; } // 枚举从 start 开始的所有可能子串结束位置 for (int end start; end s.length(); end) { // 判断子串 s[start..end] 是否为回文 if (isPalindrome(s, start, end)) { path.add(s.substring(start, end 1)); // 加入回文子串 backtrack(s, end 1, path, res); // 递归分割剩余部分 path.remove(path.size() - 1); // 回溯撤销选择 } } } // 判断 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; } }解题思路1回溯法 回文判断回溯核心逻辑start表示当前分割的起始位置当start s.length()时说明已将整个字符串分割为回文子串将当前路径加入结果集。遍历从start到末尾的所有end若s[start..end]是回文则将其加入路径递归处理end1位置之后回溯撤销选择。回文判断isPalindrome双指针法从两端向中间遍历若所有对称位置字符都相等则为回文时间复杂度 O(n)。优化提示可预处理回文子串动态规划将回文判断优化为 O(1)提升效率。import java.util.ArrayList; import java.util.List; class Solution { public ListListString partition(String s) { ListListString res new ArrayList(); ListString path new ArrayList(); // 第一步DP 预处理所有回文子串 O(1) 查询 boolean[][] dp getPalindromeDP(s); // 第二步回溯枚举所有分割方案 backtrack(s, 0, path, res, dp); return res; } // 回溯从 start 位置开始分割 private void backtrack(String s, int start, ListString path, ListListString res, boolean[][] dp) { // 递归终止整个字符串分割完成 if (start s.length()) { res.add(new ArrayList(path)); return; } // 枚举所有结束位置 end for (int end start; end s.length(); end) { // O(1) 判断是不是回文 if (dp[start][end]) { path.add(s.substring(start, end 1)); backtrack(s, end 1, path, res, dp); path.remove(path.size() - 1); // 回溯 } } } // DP 预处理生成回文表 private boolean[][] getPalindromeDP(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 (i j) { dp[i][j] true; // 单个字符一定是回文 } else if (j i 1) { dp[i][j] s.charAt(i) s.charAt(j); // 两个字符 } else { dp[i][j] (s.charAt(i) s.charAt(j) dp[i 1][j - 1]); } } } return dp; } }解题思路2回溯 DP 预处理回文51. N 皇后class Solution { public ListListString solveNQueens(int n) { ListListString res new ArrayList(); // 用数组记录每行皇后所在列row[i] j 表示第 i 行皇后在第 j 列 int[] row new int[n]; // 用三个布尔数组分别标记列、主斜线、副斜线是否被占用 boolean[] usedCol new boolean[n]; boolean[] usedDiag1 new boolean[2 * n - 1]; // row - col (n-1) 映射到 0~2n-2 boolean[] usedDiag2 new boolean[2 * n - 1]; // row col 映射到 0~2n-2 backtrack(0, n, row, usedCol, usedDiag1, usedDiag2, res); return res; } // row当前处理到第几行 private void backtrack(int row, int n, int[] rowQueen, boolean[] usedCol, boolean[] usedDiag1, boolean[] usedDiag2, ListListString res) { // 终止条件所有行处理完毕生成棋盘 if (row n) { res.add(generateBoard(rowQueen, n)); return; } // 尝试在当前行的每一列放置皇后 for (int col 0; col n; col) { int diag1 row - col (n - 1); // 主斜线映射 int diag2 row col; // 副斜线映射 // 检查列、主斜线、副斜线是否冲突 if (!usedCol[col] !usedDiag1[diag1] !usedDiag2[diag2]) { // 放置皇后 rowQueen[row] col; usedCol[col] true; usedDiag1[diag1] true; usedDiag2[diag2] true; // 递归处理下一行 backtrack(row 1, n, rowQueen, usedCol, usedDiag1, usedDiag2, res); // 回溯撤销选择 usedCol[col] false; usedDiag1[diag1] false; usedDiag2[diag2] false; } } } // 根据 rowQueen 生成题目要求的棋盘格式 private ListString generateBoard(int[] rowQueen, int n) { ListString board new ArrayList(); for (int i 0; i n; i) { char[] line new char[n]; for (int j 0; j n; j) { line[j] (rowQueen[i] j) ? Q : .; } board.add(new String(line)); } return board; } }解题思路回溯法 位 / 集合约束检查约束标记usedCol[]标记某列是否已有皇后usedDiag1[]标记主斜线row - col方向是否被占用通过row - col (n-1)映射到非负索引usedDiag2[]标记副斜线row col方向是否被占用回溯逻辑逐行处理在当前行尝试所有合法列位置若位置合法则放置皇后递归处理下一行递归结束后回溯撤销当前皇后的占用标记棋盘生成根据rowQueen数组逐行构建Q和.组成的字符串列表。