leetcode-搜索

BFS

广度优先搜索一层一层地进行遍历，每层遍历都是以上一层遍历的结果作为起点，遍历一个距离能访问到的所有节点。需要注意的是，遍历过的节点不能再次被遍历。

第一层：

• 0 -> {6,2,1,5}

第二层：

• 6 -> {4}
• 2 -> {}
• 1 -> {}
• 5 -> {3}

第三层：

• 4 -> {}
• 3 -> {}

每一层遍历的节点都与根节点距离相同。设 di 表示第 i 个节点与根节点的距离，推导出一个结论：对于先遍历的节点 i 与后遍历的节点 j，有 di <= dj。利用这个结论，可以求解最短路径等。

最优解 问题：第一次遍历到目的节点，其所经过的路径为最短路径。应该注意的是，使用 BFS 只能求解无权图的最短路径，无权图是指从一个节点到另一个节点的代价都记为 1。

在程序实现 BFS 时需要考虑以下问题：

• 队列：用来存储每一轮遍历得到的节点；
• 标记：对于遍历过的节点，应该将它标记，防止重复遍历。

二进制矩阵中的最短路径

力扣

import cn.hutool.core.lang.Pair;

import java.util.LinkedList;
import java.util.Queue;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return -1;
        }

        int[][] directions = {{-1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 0}, {0, -1}, {-1, 1}, {1, -1}};
        int m = grid.length, n = grid[0].length;
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>(0, 0));
        int pathLength = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            pathLength++;
            while (size-- > 0) {
                Pair<Integer, Integer> cur = queue.poll();
                int cr = cur.getKey(), cc = cur.getValue();
                if (grid[cr][cc] == 1) {
                    continue;
                }
                //到达终点,终止条件
                if (cr == m - 1 && cc == n - 1) {
                    return pathLength;
                }
                //直接用1来标记不能通过
                grid[cr][cc] = 1;
                for (int[] dic : directions) {
                    int nr = cr + dic[0], nc = cc + dic[1];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                        continue;
                    }
                    queue.add(new Pair<>(nr, nc));
                }
            }
        }
        return -1;
    }
}

完全平方数

力扣

class Solution {
    public int numSquares(int n) {
        List<Integer> squares = new ArrayList<>();
        int square = 1, diff = 3;
        //1，4，9...
        while (square <= n) {
            squares.add(square);
            square += diff;
            diff += 2;
        }
        Queue<Integer> queue = new LinkedList<>();
        boolean[] marked = new boolean[n + 1];
        int level = 0;
        queue.add(n);
        marked[n] = true;
        while (!queue.isEmpty()) {
            //广度优先，队列所有都要取出来
            int size = queue.size();
            level++;
            while (size-- > 0) {
                int cur = queue.poll();
                for (int s : squares) {
                    int next = cur - s;
                    //从大到小，后面的一定都小于0，所以可以break
                    if (next < 0) {
                        break;
                    }
                    if (next == 0) {
                        return level;
                    }
                    if (marked[next]) {
                        continue;
                    }
                    marked[next] = true;
                    queue.add(next);
                }
            }
        }
        //n个1
        return n;
    }
}

单词接龙

力扣

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        wordList.add(beginWord);
        int N = wordList.size();
        int start = N - 1;
        int end = 0;
        while (end < N && !wordList.get(end).equals(endWord)) {
            end++;
        }
        if (end == N) {
            return 0;
        }
        List<Integer>[] graphic = buildGraphic(wordList);
        return getShortestPath(graphic, start, end);
    }

    private List<Integer>[] buildGraphic(List<String> wordList) {
        int N = wordList.size();
        List<Integer>[] graphic = new List[N];
        for (int i = 0; i < N; i++) {
            graphic[i] = new ArrayList<>();
            for (int j = 0; j < N; j++) {
                if (isConnect(wordList.get(i), wordList.get(j))) {
                    graphic[i].add(j);
                }
            }
        }
        return graphic;
    }

    private boolean isConnect(String s1, String s2) {
        int diffCnt = 0;
        for (int i = 0; i < s1.length() && diffCnt <= 1; i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diffCnt++;
            }
        }
        return diffCnt == 1;
    }

    private int getShortestPath(List<Integer>[] graphic, int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] marked = new boolean[graphic.length];
        queue.add(start);
        marked[start] = true;
        int path = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            path++;
            while (size-- > 0) {
                int cur = queue.poll();
                for (int next : graphic[cur]) {
                    if (next == end) {
                        return path;
                    }
                    if (marked[next]) {
                        continue;
                    }
                    marked[next] = true;
                    queue.add(next);
                }
            }
        }
        return 0;
    }

}

//BFS
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(!wordList.contains(endWord)){
            return 0;
        }
        //已经访问过的结点
        Set<String> visited = new HashSet<>();
        //当前要访问结点存进的队列
        Queue<String> queue =new LinkedList<>();
        queue.offer(beginWord);
        visited.add(beginWord);
        int count=0;
        while(queue.size()>0){
            int size=queue.size();
            ++count;
            //在当前要访问结点存进的队列里开始逐个检验，并且把结点的下一层放进队列里，BFS
            for(int i=0;i<size;i++){
                //每次都是最新要比较的单词 start
                String start=queue.poll();
                //因为有的单词已经遍历过，有的单词不满足转换会跳过，所以整个wordList遍历一次
                for(String s:wordList){
                    //已遍历过，跳过看下一个单词
                    if(visited.contains(s)){
                        continue;
                    }
                    //不能转换一个字母变成这个单词的，也跳过
                    if(!canConvert(start,s)){
                        continue;
                    }
                    //没遍历过，又能转换的，当是最后转换成endWord时
                    if(s.equals(endWord)){
                        return ++count;
                    }
                    //没遍历过，又能转换的，还没到最后的end的
                    //存进visited，放入队列之后搜索
                    visited.add(s);
                    queue.offer(s);
                }
            }
        }
        return 0;
    }
    public boolean canConvert(String s1,String s2){
        if(s1.length()!=s2.length()){
            return false;
        }
        int count=0;
        for(int i=0;i<s1.length();i++){
            if(s1.charAt(i)!=s2.charAt(i)){
                count++;
                if(count>1){
                    return false;
                }
            }
        }
        return true;
    }
}

DFS

广度优先搜索一层一层遍历，每一层得到的所有新节点，要用队列存储起来以备下一层遍历的时候再遍历。

而深度优先搜索在得到一个新节点时立即对新节点进行遍历：从节点 0 出发开始遍历，得到到新节点 6 时，立马对新节点 6 进行遍历，得到新节点 4；如此反复以这种方式遍历新节点，直到没有新节点了，此时返回。返回到根节点 0 的情况是，继续对根节点 0 进行遍历，得到新节点 2，然后继续以上步骤。

从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种 可达性 问题。

在程序实现 DFS 时需要考虑以下问题：

• 栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
• 标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。

岛屿的最大面积

力扣

class Solution {
    private int m, n;
    private int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        m = grid.length;
        n = grid[0].length;
        int maxArea = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxArea = Math.max(maxArea, dfs(grid, i, j));
            }
        }
        return maxArea;
    }

    private int dfs(int[][] grid, int r, int c) {
        //终止条件
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
            return 0;
        }
        //标记
        grid[r][c] = 0;
        int area = 1;
        for (int[] d : directions) {
            area += dfs(grid, r + d[0], c + d[1]);
        }
        return area;
    }
}

岛屿数量

力扣

class Solution {
    private int m, n;
    private int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        m = grid.length;
        n = grid[0].length;
        int islandsNum = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '0') {
                    dfs(grid, i, j);
                    islandsNum++;
                }
            }
        }
        return islandsNum;
    }

    private void dfs(char[][] grid, int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == '0') {
            return;
        }
        grid[r][c] = '0';
        for (int[] d : directions) {
            dfs(grid, r + d[0], c + d[1]);
        }
    }
}

朋友圈

力扣

class Solution {
    private int n;

    public int findCircleNum(int[][] M) {
        n = M.length;
        int circleNum = 0;
        boolean[] isVisited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!isVisited[i]) {
                dfs(M, i, isVisited);
                circleNum++;
            }
        }
        return circleNum;
    }

    private void dfs(int[][] M, int i, boolean[] isVisited) {
        isVisited[i] = true;
        for (int k = 0; k < n; k++) {
            if (M[i][k] == 1 && !isVisited[k]) {
                dfs(M, k, isVisited);
            }
        }
    }
}

被围绕的区域

力扣

class Solution {
    private int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private int m, n;

    public void solve(char[][] board) {
        /**
         * 所有和边界相连的0都不能被变为x，先将与边界相连的0变为-，没被变的0就是被围绕的区域。
         */
        if (board == null || board.length == 0) {
            return;
        }
        m = board.length;
        n = board[0].length;
        for (int i = 0; i < m; i++) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for (int i = 0; i < n; i++) {
            dfs(board, 0, i);
            dfs(board, m - 1, i);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '-') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private void dfs(char[][] board, int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') {
            return;
        }
        board[r][c] = '-';
        for (int[] d : directions) {
            dfs(board, r + d[0], c + d[1]);
        }
    }
}

太平洋大西洋水流问题

力扣

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    private int m,n;
    private int[][] matrix;
    private int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        /**
         * 从边界出发
         */
        List<List<Integer>> ret = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return ret;
        }
        m = matrix.length;
        n = matrix[0].length;
        this.matrix = matrix;
        boolean[][] canReachP = new boolean[m][n];
        boolean[][] canReachA = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dfs(i, 0, canReachP);
            dfs(i, n - 1, canReachA);
        }
        for (int i = 0; i < n; i++) {
            dfs(0, i, canReachP);
            dfs(m - 1, i, canReachA);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (canReachA[i][j] && canReachP[i][j]) {
                    ret.add(Arrays.asList(i, j));
                }
            }
        }
        return ret;
    }

    private void dfs(int r, int c, boolean[][] canReach) {
        if (canReach[r][c]) {
            return;
        }
        canReach[r][c] = true;
        for (int[] d : directions) {
            int nextr = r + d[0];
            int nextc = c + d[1];
            if (nextr < 0 || nextr >= m || nextc < 0 || nextc >= n || matrix[r][c] > matrix[nextr][nextc]) {
                continue;
            }
            dfs(nextr, nextc, canReach);
        }
    }
}

回溯

Backtracking（回溯）属于 DFS。

• 普通 DFS 主要用在 可达性问题 ，这种问题只需要执行到特点的位置然后返回即可。
• 而 Backtracking 主要用于求解 排列组合 问题，例如有 { ‘a’,’b’,’c’ } 三个字符，求解所有由这三个字符排列得到的字符串，这种问题在执行到特定的位置返回之后还会继续执行求解过程。

因为 Backtracking 不是立即返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：

• 在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；
• 但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。

电话号码的字母组合

力扣

class Solution {
    private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        List<String> combinatios = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return combinatios;
        }
        doCombination(new StringBuffer(), combinatios, digits);
        return combinatios;
    }

    private void doCombination(StringBuffer prefix, List<String> combinations, final String digits) {
        //终止条件
        if (prefix.length() == digits.length()) {
            combinations.add(prefix.toString());
            return;
        }
        int curDigits = digits.charAt(prefix.length()) - '0';
        String letters = KEYS[curDigits];
        for (char c : letters.toCharArray()) {
            prefix.append(c);
            doCombination(prefix, combinations, digits);
            //回溯 复原
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }
}

复原ip地址

力扣

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> address = new ArrayList<>();
        StringBuilder tempAdress = new StringBuilder();
        doRestore(0, tempAdress, address, s);
        return address;
    }

    private void doRestore(int k, StringBuilder tempAdress, List<String> address, String s) {
        //终止条件
        if (k == 4 || s.length() == 0) {
            if (k == 4 && s.length() == 0) {
                address.add(tempAdress.toString());
            }
            return;
        }
        //三个数字为一个部分
        for (int i = 0; i < s.length() && i <= 2; i++) {
            if (i != 0 && s.charAt(0) == '0') {
                break;
            }
            String part = s.substring(0, i + 1);
            if (Integer.valueOf(part) <= 255) {
                if (tempAdress.length() != 0) {
                    part = '.' + part;
                }
                tempAdress.append(part);
                doRestore(k + 1, tempAdress, address, s.substring(i + 1));
                //回溯
                tempAdress.delete(tempAdress.length() - part.length(), tempAdress.length());
            }
        }
    }
}

单词搜索

力扣

class Solution {
    private final static int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private int m;
    private int n;

    public boolean exist(char[][] board, String word) {
        if (word == null || word.length() == 0) {
            return true;
        }
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        m = board.length;
        n = board[0].length;
        boolean[][] hasVisited = new boolean[m][n];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (backtracking(0, r, c, hasVisited, board, word)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean backtracking(int curLen, int r, int c, boolean[][] hasVisited, final char[][] board, final String word) {
        if (curLen == word.length()) {
            return true;
        }
        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(curLen) || hasVisited[r][c]) {
            return false;
        }
        hasVisited[r][c] = true;
        for (int[] d : direction) {
            if (backtracking(curLen + 1, r + d[0], c + d[1], hasVisited, board, word)) {
                return true;
            }
        }
        //回溯
        hasVisited[r][c] = false;
        return false;
    }
}

二叉树的所有路径

力扣

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<>();
        if (root == null) {
            return paths;
        }
        List<Integer> values = new ArrayList<>();
        backtracking(root, values, paths);
        return paths;
    }

    private void backtracking(TreeNode node, List<Integer> values, List<String> paths) {
        if (node == null) {
            return;
        }
        values.add(node.val);
        if (isLeaf(node)) {
            paths.add(buildPath(values));
        } else {
            backtracking(node.left, values, paths);
            backtracking(node.right, values, paths);
        }
        values.remove(values.size() - 1);
    }

    private boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }

    private String buildPath(List<Integer> values) {
        StringBuffer str = new StringBuffer();
        for (int i = 0; i < values.size(); i++) {
            str.append(values.get(i));
            if (i != values.size() - 1) {
                str.append("->");
            }
        }
        return str.toString();
    }
}

全排列

力扣

import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> permutes = new ArrayList<>();
        List<Integer> permuteList = new ArrayList<>();
        boolean[] hasVisited = new boolean[nums.length];
        backtracking(permuteList, permutes, hasVisited, nums);
        return permutes;
    }

    private void backtracking(List<Integer> pemuteList, List<List<Integer>> permutes, boolean[] hasVisited, int[] nums) {
        if (pemuteList.size() == nums.length) {
            //重新构造一个list？
            permutes.add(new ArrayList<>(pemuteList));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (hasVisited[i]) {
                continue;
            }
            hasVisited[i] = true;
            pemuteList.add(nums[i]);
            backtracking(pemuteList, permutes, hasVisited, nums);
            pemuteList.remove(pemuteList.size() - 1);
            hasVisited[i] = false;
        }
    }
}

全排列Ⅱ

力扣

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> permutes = new ArrayList<>();
        List<Integer> permuteList = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] hasVisited = new boolean[nums.length];
        backtracking(permuteList, permutes, hasVisited, nums);
        return permutes;
    }

    private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] hasVisited, int[] nums) {
        if (permuteList.size() == nums.length) {
            permutes.add(new ArrayList<>(permuteList));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            /**
             * 去重
             * 如果和前一个元素相等且前一个元素没有访问过需要跳过当前元素
             * 举例[1,1,2],如果第一个1已经访问过，那第二个1不用跳过，有[1,1,2]这种排列
             * 如果第一个1还未访问过，则第二个1在当前位置的情况在第一个1时已经涵盖到了
             * 即第一个1已经回溯过了
             */
            if (i != 0 && nums[i] == nums[i - 1] && !hasVisited[i - 1]) {
                continue;
            }
            if (hasVisited[i]) {
                continue;
            }
            hasVisited[i] = true;
            permuteList.add(nums[i]);
            backtracking(permuteList, permutes, hasVisited, nums);
            ;
            hasVisited[i] = false;
            permuteList.remove(permuteList.size() - 1);
        }
    }
}

组合总和Ⅲ

力扣

import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> combinations = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        backtracking(k, n, 1, path, combinations);
        return combinations;
    }

    private void backtracking(int k, int n, int start, List<Integer> path, List<List<Integer>> combinations) {
        if (k == 0 && n == 0) {
            combinations.add(new ArrayList<>(path));
            return;
        }
        //不符合
        if (k == 0 || n == 0) {
            return;
        }
        for (int i = start; i <= 9; i++) {
            path.add(i);
            backtracking(k - 1, n - i, i + 1, path, combinations);
            //回溯
            path.remove(path.size() - 1);
        }
    }
}

子集

力扣

import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        List<Integer> tempSubset = new ArrayList<>();
        for (int i = 0; i <= nums.length; i++) {
            backtracking(0, tempSubset, subsets, i, nums);
        }
        return subsets;
    }

    private void backtracking(int start, List<Integer> tempSubset, List<List<Integer>> subsets, final int size, final int[] nums) {
        if (size == tempSubset.size()) {
            subsets.add(new ArrayList<>(tempSubset));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            tempSubset.add(nums[i]);
            backtracking(i + 1, tempSubset, subsets, size, nums);
            tempSubset.remove(tempSubset.size() - 1);
        }
    }
}

子集Ⅱ

力扣

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> subsets = new ArrayList<>();
        List<Integer> tempSubset = new ArrayList<>();
        boolean[] hasVisited = new boolean[nums.length];
        for (int size = 0; size <= nums.length; size++) {
            backtracking(0, tempSubset, subsets, hasVisited, size, nums);
        }
        return subsets;
    }

    private void backtracking(int start, List<Integer> tempSubsets, List<List<Integer>> subsets, boolean[] hasVisited, final int size, final int[] nums) {
        if (tempSubsets.size() == size) {
            subsets.add(new ArrayList<>(tempSubsets));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (i != 0 && nums[i] == nums[i - 1] && !hasVisited[i - 1]) {
                continue;
            }
            tempSubsets.add(nums[i]);
            hasVisited[i] = true;
            backtracking(i + 1, tempSubsets, subsets, hasVisited, size, nums);
            //回溯
            tempSubsets.remove(tempSubsets.size() - 1);
            hasVisited[i] = false;
        }
    }
}

分割回文串

import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> partitions = new ArrayList<>();
        List<String> tempPatition = new ArrayList<>();
        doPartition(s, partitions, tempPatition);
        return partitions;
    }

    private void doPartition(String s, List<List<String>> partitions, List<String> tempPatition) {
        if (s.length() == 0) {
            partitions.add(new ArrayList<>(tempPatition));
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if (isPalindrome(s, 0, i)) {
                tempPatition.add(s.substring(0, i + 1));
                doPartition(s.substring(i + 1), partitions, tempPatition);
                tempPatition.remove(tempPatition.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int begin, int end) {
        while (begin < end) {
            if (s.charAt(begin++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }
}

解数独

class Solution {
    private boolean[][] rowsUsed = new boolean[9][10];
    private boolean[][] colsUsed = new boolean[9][10];
    private boolean[][] cubesUsed = new boolean[9][10];
    private char[][] board;

    public void solveSudoku(char[][] board) {
        this.board = board;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                int num = board[i][j] - '0';
                rowsUsed[i][num] = true;
                colsUsed[j][num] = true;
                cubesUsed[cubeNum(i, j)][num] = true;
            }
        }
        backtracking(0, 0);
    }

    private boolean backtracking(int row, int col) {
        while (row < 9 && board[row][col] != '.') {
            row = col == 8 ? row + 1 : row;
            col = col == 8 ? 0 : col + 1;
        }
        if (row == 9) {
            return true;
        }
        for (int num = 1; num <= 9; num++) {
            if (rowsUsed[row][num] || colsUsed[col][num] || cubesUsed[cubeNum(row, col)][num]) {
                continue;
            }
            rowsUsed[row][num] = colsUsed[col][num] = cubesUsed[cubeNum(row, col)][num] = true;
            board[row][col] = (char) (num + '0');
            //有解
            if (backtracking(row, col)) {
                return true;
            }
            //无解，回溯
            rowsUsed[row][num] = colsUsed[col][num] = cubesUsed[cubeNum(row, col)][num] = false;
            board[row][col] = '.';
        }
        return false;
    }

    private int cubeNum(int i, int j) {
        int r = i / 3;
        int c = j / 3;
        return r * 3 + c;
    }
}

N 皇后

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    private List<List<String>> solutions;
    private char[][] nQueens;
    private boolean[] colUsed;
    private boolean[] diagonals45Used;
    private boolean[] diagonals135Used;
    private int n;

    public List<List<String>> solveNQueens(int n) {
        solutions = new ArrayList<>();
        nQueens = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(nQueens[i], '.');
        }
        colUsed = new boolean[n];
        diagonals45Used = new boolean[2 * n - 1];
        diagonals135Used = new boolean[2 * n - 1];
        this.n = n;
        backtraking(0);
        return solutions;
    }

    private void backtraking(int row) {
        if (row == n) {
            List<String> list = new ArrayList<>();
            for (char[] chars : nQueens) {
                list.add(new String(chars));
            }
            solutions.add(list);
            return;
        }
        for (int col = 0; col < n; col++) {
            int diagonals45Idx = row + col;
            int diagonals135Idx = n - 1 - (row - col);
            if (colUsed[col] || diagonals45Used[diagonals45Idx] || diagonals135Used[diagonals135Idx]) {
                continue;
            }
            nQueens[row][col] = 'Q';
            colUsed[col] = diagonals135Used[diagonals135Idx] = diagonals45Used[diagonals45Idx] = true;
            backtraking(row + 1);
            //回溯
            colUsed[col] = diagonals135Used[diagonals135Idx] = diagonals45Used[diagonals45Idx] = false;
            nQueens[row][col] = '.';
        }
    }
}