Why using HashSet exceeds the time limit?


  • 0
    Z

    Hi, it's smart to use a two-dimensional array and a special character like '#' to save the visited positions.
    But if I want to use HashSet to record the position I visited, my code will get a TLE.

    I think the contain method, add method and remove method of JAVA HashSet all runs in O(1) expected time. It's wired it got a TLE but using two-dimensional array didn't.

    Can anyone help me with this? Here is my code.

    public class Solution {
        Set<Integer> set = new HashSet<>();
        public boolean exist(char[][] board, String word) {
            
            for(int i = 0; i < board.length; i++){
                for(int j = 0; j < board[i].length; j++){
                    if(word.charAt(0) == board[i][j]){
                        if (search(board, word, i, j, 0)) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
        
        private boolean search(char[][]board, String word, int i, int j, int index){
            if(index == word.length()){
                return true;
            }
            
            if(i >= board.length || i < 0 || j >= board[i].length || j < 0 || board[i][j] != word.charAt(index) || set.contains(i*10 + j)){
                return false;
            }
            
            set.add(i*10 + j);
            if(search(board, word, i-1, j, index+1) || 
               search(board, word, i+1, j, index+1) ||
               search(board, word, i, j-1, index+1) || 
               search(board, word, i, j+1, index+1)){
                return true;
            }
            
            set.remove(i*10 + j);
            return false;
        }
    }
    

Log in to reply
 

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