Same algorithm implemented in two ways. One is AC, the other is TLE(but runs well on my own computer). WHY???


  • 0
    Z

    I implement one algorithm(DFS) in two ways.
    1:

    class Solution {
    public:
        bool isValid(const vector<vector<char> > &board, int i, int j) {
            unordered_set<char> hs;
            for(int k = 0; k < 9; ++k) {
                char t = board[i][k];
                if(t == '.')
                    continue;
                if(hs.find(t) != hs.end()) {
                    return false;
                } else {
                    hs.insert(t);
                }
            }
            hs.clear();
            for(int k = 0; k < 9; ++k) {
                char t = board[k][j];
                if(t == '.')
                    continue;
                if(hs.find(t) != hs.end()) {
                    return false;
                } else {
                    hs.insert(t);
                }
            }
            hs.clear();
            int m = i / 3 * 3;
            int n = j / 3 * 3;
            for(int mm = m; mm < m + 3; ++mm) {
                for(int nn = n; nn < n + 3; ++nn) {
                    char t = board[mm][nn];
                    if(t == '.')
                        continue;
                    if(hs.find(t) != hs.end()) {
                        return false;
                    } else {
                        hs.insert(t);
                    }
                }
            }
            return true;
        }
        
        bool helper(vector<vector<char> > &board, int m, int n) {
            int i = m, j = n;
            bool isPoint = false;
            //find the next '.' location from m, n in the order of
            //               m,n------------------>end
            //start------------------------------->end
            //start------------------------------->end
            for(; i < board.size(); ++i) {
                for(; j < board[0].size(); ++j) {
                    if(board[i][j] == '.') {
                        isPoint = true;
                        break;
                    }
                }
                if(isPoint)
                    break;
                j = 0;
            }
            if(i == board.size())//completed
                return true;
            for(int k = 1; k < 10; ++k) {//try 1~9 in i, j
                board[i][j] = k + '0';
                if(isValid(board, i, j)) {
                    if(helper(board, i, j))
                        return true;
                }
                board[i][j] = '.';
            }
            return false;
        }
        
        void solveSudoku(vector<vector<char> > &board) {
            helper(board, 0, 0);
        }
    };
    

    This is TLE implementation:
    Last executed input: [".....7..9",".4..812..","...9...1.","..53...72","293....5.",".....53..","8...23...","7...5..4.","531.7...."]

    I ran this sample using this period of code in my own computer and I got the correct result.

    /This implementation is Accepted***/

    class Solution {
    public:
        bool isValid(vector<vector<char> > &board, int r, int c, char v) {
            for(int j = 0; j < 9; ++j) {
                if(j != c && board[r][j] == v)
                    return false;
            }
            for(int i = 0; i < 9; ++i) {
                if(i != r && board[i][c] == v)
                    return false;
            }
            for(int i = 3 * (r / 3); i < 3 * (r / 3) + 3; ++i) {
                for(int j = 3 * (c / 3); j < 3 * (c / 3) + 3; ++j) {
                    if((i != r || j != c) && v == board[i][j])
                        return false;
                }
            }
            return true;
        }
    
        bool solveSudokuHelper(vector<vector<char> > &board) {
            for(int i = 0; i < 9; ++i) {
                for(int j = 0; j < 9; ++j) {
                    if(board[i][j] == '.') {
                        for(int k = 0; k < 9; ++k) {
                            if(isValid(board, i, j, '1' + k)) {
                                board[i][j] = '1' + k;
                                if(solveSudokuHelper(board))
                                    return true;
                                board[i][j] = '.';
                            }
                        }
                        return false;
                    }
                }
            }
            return true;
        }
        
        void solveSudoku(vector<vector<char> > &board) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
            solveSudokuHelper(board);
        }
    };
    

    I think both implementations use the same algorithm. Why does the latter one works while the first one does not??


  • 0
    S

    I had the same issue with you. I tried to change the isValid function and finally it worked out. I think it's because the operations on unordered_set is slower than validating the board using for loop directly.


Log in to reply
 

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