My java code got a Time Limit Exceeded! How can I make a promotion?


  • 0
    C
    public class Solution {
    public boolean exist(char[][] board, String word) {
    	int lenX = board.length;
    	int lenY = board[0].length;
    	boolean result = false;
    	int[][] location = new int[lenX][lenY];
    	for (int i = 0; i < lenX; i++) {
    		for (int j = 0; j < lenY; j++) {
    			location[i][j] = 0;
    		}
    	}
    
    	for (int i = 0; i < lenX; i++) {
    		for (int j = 0; j < lenY; j++) {
    			if (board[i][j] == word.charAt(0)) {
    				location[i][j] = 1;
    				result = searchNext(board, location, 1, word, i, j);
                    if(result == true) {
                        return true;
                    }
    			}
    		}
    	}
    
    	return false;
    }
    
    public boolean searchNext(char[][] board, int[][] location, int chAt,
    		String word, int x, int y) {
    
    	System.out.println("the location is : " + x + " " + y);
    	boolean result = false;
    	if (chAt == word.length()) {
    		return true;
    	}
    	int nextAt = chAt + 1;
    	if ((y > 0) && (location[x][y - 1] != 1)
    			&& (board[x][y - 1] == word.charAt(chAt))) {
    		location[x][y - 1] = 1;
    		result = searchNext(board, location, nextAt, word, x, y - 1);
    		if (result == true) {
    			return true;
    		}
    	}
    
    	if ((y < board[0].length - 1) && (location[x][y + 1] != 1)
    			&& (board[x][y + 1] == word.charAt(chAt))) {
    		location[x][y + 1] = 1;
    		result = searchNext(board, location, nextAt, word, x, y + 1);
    		if (result == true) {
    			return true;
    		}
    	}
    
    	if ((x > 0) && (location[x - 1][y] != 1)
    			&& (board[x - 1][y] == word.charAt(chAt))) {
    		location[x - 1][y] = 1;
    		result = searchNext(board, location, nextAt, word, x - 1, y);
    		if (result == true) {
    			return true;
    		}
    	}
    
    	if ((x < board.length - 1) && (location[x + 1][y] != 1)
    			&& (board[x + 1][y] == word.charAt(chAt))) {
    		location[x + 1][y] = 1;
    		result = searchNext(board, location, nextAt, word, x + 1, y);
    		if (result == true) {
    			return true;
    		}
    	}
    	location[x][y] = 0;
    	return false;
    }
    

    }

    This is my code, use DFS and matrix location[][] is used to save if this point was used.


  • 1
    S

    Remove this line System.out.println("the location is : " + x + " " + y);.

    See question Am I allowed to print something to stdout? in OJ FAQ.


  • 0
    C

    Yeah~ You are right !! Thx~


  • 0
    L

    There's judgement to make sure every step is in the board, such as if ((x < board.length - 1) && (location[x + 1][y] != 1), we can create a bigger board, whose boundary elements are all non-letter characters but the inside is same as the original board. So we can start at any inside elements and don't need to worry about the boundary:

    0     0          0        ....        0             0
    
    0 board[0][0]  board[0][1] .... board[0][n]          0
    

    ....


Log in to reply
 

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