What is difference between these two codes


  • 0
    A

    I wrote this recursion version, and got TLE, I thought it was because stack overflow. But when I googled it and found it could pass with recursion version. I modified it to the second one, and passed it, But I don't see any difference. Could someone just look at it and give me any advice please? Thanks!!

    Version 1:

    public class WordSearch {
    public boolean exist(char[][] board, String word) {
    	if(board == null || word == null || board.length == 0 || board[0].length == 0 || word.length() == 0){
    		return false;
    	}
    	int row = board.length;
    	int col = board[0].length;
    	boolean[][] visited = new boolean[row][col];
    	char c = word.charAt(0);
    	for(int i = 0; i < board.length; i++) {
    		for(int j = 0; j < board[0].length; j++) {
    			char ch = board[i][j];
    			if(c == ch) {
    				boolean ret = existHelp(board, word, 1, i, j, visited); 
    				if(ret) {
    					return true;
    				}
    			}
    		}
    	}
    	return false;
    }
    boolean existHelp(char[][] board, String word, int len, int x, int y, boolean[][] visited) {
    	if(len >= word.length()) {
    		return true;
    	}
    	if(x >= board.length || y >= board[0].length) {
    		return false;
    	}
    	visited[x][y] = true;
    	char c = word.charAt(len);
    	boolean left, right, up, down;
    	left = right = up = down = false;
    	if(x + 1 < board.length && board[x + 1][y] == c && visited[x + 1][y] == false) {
    		
    		up =  existHelp(board, word, len + 1, x + 1, y, visited);
    	}
    	if(x - 1 >= 0 && board[x - 1][y] == c && visited[x - 1][y] == false) {
    		
    		down =  existHelp(board, word, len + 1, x - 1, y, visited);
    	} 
    	if(y + 1 < board[0].length && board[x][y + 1] == c && visited[x][y + 1] == false) {
    		
    		 right =  existHelp(board, word, len + 1, x, y + 1, visited);
    	}
    	if(y - 1 >= 0 && board[x][y - 1] == c && visited[x][y - 1] == false) {
    		
    	   left =  existHelp(board, word, len + 1, x, y - 1, visited);
    	}
    	visited[x][y] = false;
    	return left || right || up || down;
    	
    }
    

    Version 2 (just existHelp method. Exist method is the same):

    boolean existHelp(char[][] board, String word, int len, int x, int y, boolean[][] visited) {
    	if(len >= word.length()) {
    		return true;
    	}
    	if(x < 0 || y < 0 || x >= board.length || y >= board[0].length) {
    		return false;
    	}
    	if(visited[x][y] == true) {
    	    return false;
    	}
    	
    	if(word.charAt(len) != board[x][y]) {
    	    return false;
    	}
    	visited[x][y] = true;
    	char c = word.charAt(len);
    	
        boolean res =  (existHelp(board, word, len + 1, x + 1, y, visited) ||
    	     existHelp(board, word, len + 1, x - 1, y, visited) ||
    	     existHelp(board, word, len + 1, x, y + 1, visited) ||
             existHelp(board, word, len + 1, x, y - 1, visited) );
             
             visited[x][y] = false;
        
        return res;
    }

  • 0
    R

    Your first version checked twice. So it got TLE.


  • 0
    C

    Hi, the biggest difference between version 1 and version 2 algorithm is the stop condition. In version 1, the existHelp function need to get all left, right, up and down variable result before return. Therefore the algorithm will search all possible solutions every time and it will cost a lot of time. In version 2, you use a or condition to get the res variable and it will stop if any existHelp function return true. You can try to modify version 1 existHelp function to return early as soon as you got a true return from recursive function call.


  • 0
    A

    Very clear explanation. Thanks a lot!


Log in to reply
 

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