JAVA Clean DFS version,,, for real


  • 0
    L
    class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> res = new ArrayList();
            ArrayList<String> cur = new ArrayList();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) sb.append('.');
            for (int i = 0; i < n; i++) cur.add(sb.toString());
            helper(n, 0, cur, res);
            return res;
        }
        public void helper(int n, int row, ArrayList<String> cur, List<List<String>> res) {
            if (row == n) {
                List<String> toAdd = new ArrayList();
                for (int i = 0; i < cur.size(); i++) toAdd.add(cur.get(i));
                res.add(toAdd);
                return;
            }
            for (int j = 0; j < n; j++) {
                if (isValid(n, cur, row, j)) {
                    StringBuilder sb = new StringBuilder(cur.get(row));
                    sb.setCharAt(j, 'Q');
                    cur.set(row, sb.toString());
                    helper(n, row+1, cur, res);
                    sb.setCharAt(j, '.');
                    cur.set(row, sb.toString());
                }
            }
        }
        public boolean isValid(int n, ArrayList<String> cur, int row, int col) {
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < n; j++) {
                    if (cur.get(i).charAt(j) == 'Q' && (j == col || Math.abs(row-i) == Math.abs(col-j))) return false;
                }
            }
            return true;
        }
    };
    

    How do you think of it?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.