36. Valid Sudoku

problem description

Determine if a 9x9 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 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Input:
[
  ["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:
[
  ["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.

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.

• The given board contain only digits 1-9 and the character '.'.

• The given board size is always 9x9.

algorithm thought

使用hash表存放之前访问过的信息，可以保证每个位置只访问一次。这也类似一些一维数组题目，需要我们在O(n)时间复杂度内解决问题。这里需要保存数独规则下，当前位置对后面位置的影响。在数独中，行和列以及block中不能出现一样的数字。每次将访问的数字3个规则保存到hash表中，这种思路其实不难得出，难得出的是该如果在hash表中保存信息。如何保存可以看代码。

code

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<string> st;
        for(int i=0;i<board.size();++i){
            for(int j=0;j<board[0].size();++j){
                if(board[i][j]!='.'){
                    string tmp="(";tmp.push_back(board[i][j]);tmp+=")";
                    string ro=to_string(i)+tmp;
                    string col=tmp+to_string(j);
                    string mid=to_string(i/3)+tmp+to_string(j/3);
                    if(st.count(ro)||st.count(col)||st.count(mid)){
                        //cout<<ro<<' '<<col<<' '<<mid<<' ';
                        return false;
                    }
                    st.insert(ro);st.insert(col);st.insert(mid);
                }
            }
        }
        return true;
    }
};

algorithm analysis

算法中有两个for循环，循环中进行的操作是O(1)的，最后时间复杂度是O(n²)