Java time limit exceeded


  • 0
    K

    I'm getting time limit exceeded and I have no idea why, because when I compare it to other Java solutions, they do the exact same thing, except mine is too slow. any ideas why? I looked at this one which runs in 270 ms which is the exact same idea as mine

    public class Solution {
        int rMax = 0;
        int cMax = 0;
        public boolean exist(char[][] board, String word) {
            
            if(board.length == 0 || word.length() == 0) {
                return false;
            }
            rMax = board.length;
            cMax = board[0].length;
            char firstLetter = word.charAt(0);
            for(int row = 0; row < rMax; row++) {
                for(int col = 0; col < cMax; col++) {
                    if(checkExists(board,row, col, new HashSet<Pair>(), word))
                        return true;
                }
            }
            return false;
        }
        
        public boolean checkExists(char[][] board, int row, int col, HashSet<Pair> traversedPairs, String word ) {
            if(word.length() == 0) return true;
            if( inRange(row,col) && !traversedPairs.contains(new Pair(row,col)) && board[row][col] == word.charAt(0)) {
                traversedPairs.add(new Pair(row,col));
                
                String wordOmitFirst = word;
                if(wordOmitFirst.length() == 1) wordOmitFirst = "";
                else{
                    wordOmitFirst = wordOmitFirst.substring(1);
                }
                boolean left =  checkExists(board, row, col-1, new HashSet<Pair>(traversedPairs), wordOmitFirst);
                if(left) return true;
                boolean up = checkExists(board, row-1, col, new HashSet<Pair>(traversedPairs), wordOmitFirst);
                if(up) return true;
                boolean right = checkExists(board, row, col+1, new HashSet<Pair>(traversedPairs), wordOmitFirst);
                if(right) return true;
                boolean down = checkExists(board, row+1, col, new HashSet<Pair>(traversedPairs), wordOmitFirst);
                if(down) return true;
    
            }
            return false;
        }
        
        public boolean inRange(int row, int col) {
            if(row >= 0 && row < rMax && col >= 0 && col < cMax) {
                return true;
            }
            return false;
        }
        private class Pair {
            int row;
            int col;
            public Pair(int row, int col) {
                this.row=row;
                this.col=col;
            }
     
            @Override
            public boolean equals(Object p) {
                if(!(p instanceof Pair)) {
                    return false;
                }
                //p is Pair
                
                
                
                if(this.row==((Pair)p).row && this.col == ((Pair)p).col) {
                    return true;
                }
                return false;
            }
            @Override
            public int hashCode() {
                return new Integer(row).hashCode() + new Integer(col).hashCode();
            }
        }
    }
    

  • 0
    S

    I get time limit exceeded sometimes but it passes the tests on other occasions without any code change. Looks like the timing is being affected by load on the server. Please let me know if any of you have any thoughts on why this is happening.

    public boolean exist(char[][] board, int x, int y, boolean[][] used, String word) {
    	
    	if(word.length() == 0){
    		return true;
    	}
    	
    	if(board[x][y] == word.charAt(0) && !used[x][y]){
    		used[x][y] = true;
    		if(word.length() == 1){
    			return true;
    		}
    		String subWord = word.substring(1);
    		if(x+1 < board.length && exist(board, x+1, y, used,subWord)){
    			return true;
    		}
    		if(y+1 < board[0].length && exist(board, x, y+1, used, subWord)){
    			return true;
    		}
    		if(x-1 >= 0 &&exist(board, x-1, y, used, subWord)){
    			return true;
    		}
    		if(y-1 >= 0 && exist(board, x, y-1, used, subWord)){
    			return true;
    		}
    		used[x][y] = false;
    	}
    	return false;
    }
    
    
    public boolean exist(char[][] board, String word) {
    	if(board == null || board.length == 0){
    		return false;
    	}
    	int m = board.length;
    	int n = board[0].length;
    	for(int i = 0 ; i < m ; i++){
    		for(int j = 0 ; j < n ; j++){
    			if(exist(board, i, j, new boolean[m][n], word)) return true;
    		}
    	}
    	return false;
    }

  • 0
    Y

    {if(exist(board, i, j, new boolean[m][n], word))}
    I am wondering is it necessary to initiate a new m * n boolean matrix every loop?


  • 0
    Q

    You're generating new HashSets every single recursive call.


  • 0
    K

    But doesn't generating a new hashset only affect space, not time?


  • 0
    Q

    It takes time to generate hashset, and copy everything into it from another hashset.


Log in to reply
 

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