# What is difference between these two codes

• 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;
}``````

• Your first version checked twice. So it got TLE.

• 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.

• Very clear explanation. Thanks a lot!

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