Leetcode 36. Valid Sudoku

###### tags: `Hash Table` <h1> Leetcode 36. Valid Sudoku </h1> <ol> <li>問題描述</li> Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: 1. Each row must contain the digits 1-9 without repetition. 2. Each column must contain the digits 1-9 without repetition. 3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition. Note: A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules. Example 1: Input: board = [["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"]] Output: true Example 2: Input: board = [["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"]] Output: false Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid. <li>Input的限制</li> <ul> <li>board.length == 9</li> <li>board[i].length == 9</li> <li>board[i][j] is a digit 1-9 or '.'.</li> </ul> <li>思考流程</li> <ul> <li>Hash Set</li> 數獨的規則是每列的數字不能重複、每行的數字不能重複、每個小 3x3 宮格內的數字不能重複。假設數獨板是一個 9 x 9 的大小，這意味著，我們必須準備 27 個容器來檢查這些數字有沒有重複。然後，我們從左上方開始遍歷數獨板內的每一個數字，檢查它在所在的 row, column, and block 內是否已經有出現過，若有 return False，否則就將此數字加入到所屬的 row, column, block 內。檢查完數獨板內所有數字皆合法，就 return True。 因為 input board 的限制是 9x9 的大小，所以 time complexity 和 space complexity 皆是 O(1)。但如果我們假設數獨板的長度為 n，其 block 的格子數也是為 n，則因為要掃過數獨板的每一個數字，則 time complexity 為 O(n^2)。而我們會準備 3 個數獨板大小的空間來記錄這些數字的出現，故 space complexity 為 O(n^2)。 Time Complexity: O(n^2); Space Complexity: O(n^2) <li>Bitmasking</li> Bitmasking 作法概念其實與 hash set 差別不大，只是 hash set 最差會準備 3 * N^2 個 space 來儲存數字是否出現在各自的 row, col, and block；而 bitmasking 則是準備了 3 * N 個整數來儲存數字的狀態。 一樣 bitmasking 需要把數獨板的每個數字掃過一遍，在檢查是否出現過的時候，索引 0 ~ N-1 對應到數字 1 ~ N，我們計算出該數字應該對應的 bit 位置，對儲存整數進行 bitwise and 操作( 只有需要檢查的數字之 bit 為 1，其他 bits 皆為 0 )，若該數字已經出現過，則 return False；若未出現過則對該整數進行 bitwise or 操作，將其記錄起來。對 row, column, and block 都檢查過後，即可換下一個數字。 Time Complexity: O(n^2); Space Complexity: O(n) </ul> <li>測試</li> <ul> <li>Invalid element in board( edge case )</li> 如果數獨板內出現非"." and 1~9 的字元，則必須回報錯誤 input board 訊息。 </ol>