单词搜索(079)

class Solution {
    int m, n;
    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        char[] words = word.toCharArray();
        for(int i = 0; i = m || col = n || board[row][col] != words[idx]) return false;
        if (idx == words.length -1) return true;
        board[row][col] = '0';
        boolean status = backTrace(idx+1, row+1, col, board, words) || backTrace(idx+1, row, col+1, board, words)||
                         backTrace(idx+1, row-1, col, board, words) || backTrace(idx+1, row, col-1, board, words);
        board[row][col] = words[idx];
        return status;
    }
}

• 分析

简单回溯, 开开胃

分割回文串(131)

class Solution {
    List> res = new ArrayList();
    List path = new ArrayList();
    public List> partition(String s) {
        backTrace(0, s);
        return res;    
    }

    private void backTrace(int idx, String s){
        if (idx == s.length()){
            res.add(new ArrayList(path));
            return;
        }
        for (int j = idx; j 

• 分析

判断是否为回文串, 若是则分割

N皇后(051)

class Solution {
    List> res = new ArrayList();
    public List> solveNQueens(int n) {
        int[] queens = new int[n];
        boolean[] column = new boolean[n];
        boolean[] attaRig = new boolean[2*n];
        boolean[] attaLef = new boolean[2*n];
        backTrace(0, queens, column, attaLef, attaRig);
        return res;
    }

    private void backTrace(int row, int[] queens, boolean[] column, boolean[] attaLef, boolean[] attaRig ){
        int n = column.length;
        if (row == n){
            List temp = new ArrayList(n);
            for(int col : queens){
                char[] rowArray = new char[n];
                Arrays.fill(rowArray, '.');
                rowArray[col] = 'Q';
                temp.add(new String(rowArray));
            }
            res.add(temp);
            return;
        }

        for (int col = 0; col 

• 分析

N皇后带来了一个条件 →

• 行不相容 →以行遍历, 一行只插入一个元素
• 列, 对角线不相容 → Boolean数组来标记

灵神太强大了