8ms Java Solution 97th percentile


  • 0
    A

    I'm not surprised to see my solution ended up similar to many others.
    One fun trick I applied to mine was the way I detected collisions.
    I did not use an auxiliary memory grid. Instead I mutated the given board temporarily and put it back when I was done. As my code visits a node (preorder), it marks it as visited by setting the character to '\0', then when trying to run over that character it mismatches and bails out. Then postorder I put the character back. This allows us to know if we visited a node without an additional grid. Memory is reduced because we only increase the stackframe memory by 1 char, rather than preallocating an entire grid, so its constant memory instead of NxM memory. However my Space complexity here is still NxM because of the worst case stack depth of touching every element, though thats extremely unlikely its still the nature of Big-O.

    In addition to saving memory, reusing the board memory, also saved us from having to check if we've visited, since the code does that automatically by pruning aka checking if we have a match and bailing out. This assumes the given word does not contain a '\0'.

    Yay fun!

    	public boolean exists(char[][] board, String word) {
    		if (board == null)
    			return false;
    		if (board.length == 0)
    			return false;
    		if (board[0].length == 0)
    			return false;
    		int h = board.length;
    		int w = board[0].length;
    		for (int y = 0; y < h; y++)
    			for (int x = 0; x < w; x++)
    				if (existsHelper(board, word, x, y, 0))
    					return true;
    		return false;
    	}
    
    	// T = O((N*M) * (N*M)) or Quadratic O(N^2) but most likely an average case of N*M + N*M or Linear.
    	// S = N*M or Linear due to the stack depth being potentially as deep as snaking through every element.
    	private static boolean existsHelper(char[][] board, String word, int x, int y, int pos) {
    		if (y < 0 || y > board.length - 1)
    			return false;
    		else if (x < 0 || x > board[y].length - 1)
    			return false;
    
    		char bc = board[y][x];
    		if (bc != word.charAt(pos))
    			return false;
    		else if (pos == word.length() - 1)
    			return true;
    
    		boolean result = false;
    		board[y][x] = '\0';
    		if ( existsHelper(board, word, x, y - 1, pos + 1) || 
    			 existsHelper(board, word, x + 1, y, pos + 1) || 
    			 existsHelper(board, word, x, y + 1, pos + 1) || 
    			 existsHelper(board, word, x - 1, y, pos + 1))
    			result = true;
    		board[y][x] = bc;
    
    		return result;
    	}
    

Log in to reply
 

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