36. Valid Sudoku

原题：36. Valid Sudoku

方法一

思路：brute force

时间复杂度：O(n^2)

// Runtime: 96 ms, faster than 28.80% of JavaScript online submissions for Valid Sudoku.
// Memory Usage: 39.2 MB, less than 26.67% of JavaScript online submissions for Valid Sudoku.
var isValidSudoku = function (board) {
  const checkRow = function (row) {
    const set = new Set();
    for (let i = 0; i < 9; i++) {
      if (board[row][i] === ".") {
        continue;
      }
      if (set.has(board[row][i])) {
        return false;
      }
      set.add(board[row][i]);
    }

    return true;
  };

  const checkCol = function (col) {
    const set = new Set();
    for (let i = 0; i < 9; i++) {
      if (board[i][col] === ".") {
        continue;
      }
      if (set.has(board[i][col])) {
        return false;
      }
      set.add(board[i][col]);
    }

    return true;
  };

  const checkSquare = function (x, y) {
    //左上角原点
    const set = new Set();
    for (let i = x; i < x + 3; i++) {
      for (let j = y; j < y + 3; j++) {
        if (board[i][j] === ".") {
          continue;
        }
        if (set.has(board[i][j])) {
          return false;
        }
        set.add(board[i][j]);
      }
    }

    return true;
  };

  for (let i = 0; i < 9; i++) {
    if (!checkRow(i) || !checkCol(i)) {
      return false;
    }
  }

  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (!checkSquare(i * 3, j * 3)) {
        return false;
      }
    }
  }

  return true;
};

方法二（Recommend）

思路：利用set缓存每一步的结果

时间复杂度：O(n^2)，实际上比方法一通用、高效很多

// Runtime: 100 ms, faster than 25.57% of JavaScript online submissions for Valid Sudoku.
// Memory Usage: 39.4 MB, less than 26.67% of JavaScript online submissions for Valid Sudoku.
var isValidSudoku = function (board) {
  const set = new Set();
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const grid = board[i][j];
      if (grid === ".") {
        continue;
      }
      const rowKey = `row_${i}_${grid}`;
      const colKey = `col_${j}_${grid}`;
      const boxKey = `box_${~~(i / 3)}_${~~(j / 3)}_${grid}`;
      if (set.has(rowKey) || set.has(colKey) || set.has(boxKey)) {
        return false;
      }

      set.add(rowKey);
      set.add(colKey);
      set.add(boxKey);
    }
  }

  return true;
};

test cases:

test("test1", () => {
  expect(
    isValidSudoku([
      ["5", "3", ".", ".", "7", ".", ".", ".", "."],
      ["6", ".", ".", "1", "9", "5", ".", ".", "."],
      [".", "9", "8", ".", ".", ".", ".", "6", "."],
      ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
      ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
      ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
      [".", "6", ".", ".", ".", ".", "2", "8", "."],
      [".", ".", ".", "4", "1", "9", ".", ".", "5"],
      [".", ".", ".", ".", "8", ".", ".", "7", "9"],
    ])
  ).toEqual(true);
});

test("test2", () => {
  expect(
    isValidSudoku([
      ["8", "3", ".", ".", "7", ".", ".", ".", "."],
      ["6", ".", ".", "1", "9", "5", ".", ".", "."],
      [".", "9", "8", ".", ".", ".", ".", "6", "."],
      ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
      ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
      ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
      [".", "6", ".", ".", ".", ".", "2", "8", "."],
      [".", ".", ".", "4", "1", "9", ".", ".", "5"],
      [".", ".", ".", ".", "8", ".", ".", "7", "9"],
    ])
  ).toEqual(false);
});

test("test3", () => {
  expect(
    isValidSudoku([
      [".", ".", ".", ".", "5", ".", ".", "1", "."],
      [".", "4", ".", "3", ".", ".", ".", ".", "."],
      [".", ".", ".", ".", ".", "3", ".", ".", "1"],
      ["8", ".", ".", ".", ".", ".", ".", "2", "."],
      [".", ".", "2", ".", "7", ".", ".", ".", "."],
      [".", "1", "5", ".", ".", ".", ".", ".", "."],
      [".", ".", ".", ".", ".", "2", ".", ".", "."],
      [".", "2", ".", "9", ".", ".", ".", ".", "."],
      [".", ".", "4", ".", ".", ".", ".", ".", "."],
    ])
  ).toEqual(false);
});