# Exceed time limit for the case : aaaa,aaaa,........, baaaaaaaaa

• For this case, my method will only run M*N times. Why it will exceed time limit?

``````public class Solution {
private int[] xShift = new int[] {-1, 0, 0, 1};
private int[] yShift = new int[] {0, -1, 1, 0};

public boolean exist (char[][] board, String word) {
if (board == null || board.length == 0) return false;
if (word == null || word.length() == 0) return true;
if (board.length * board[0].length < word.length()) return false;

for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, word, i, j, 0)) return true;
}
}

return false;
}

private boolean dfs(char[][] board, String word, int iStart, int jStart, int index) {
if (index == word.length()) {
return true;
}

if (board[iStart][jStart] != word.charAt(index)) return false;
char curr = board[iStart][jStart];
board[iStart][jStart] = '#';

for (int k = 0; k < 4; k++) {
int i = iStart - xShift[k];
int j = jStart - yShift[k];
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length
|| board[i][j] == '#') continue;
if (dfs(board, word, i, j, index + 1)) {
//very important
board[iStart][jStart] = curr;
return true;
}
}

board[iStart][jStart] = curr;

return false;

}
}``````

``````if (board[iStart][jStart] != word.charAt(index)) return false;
else{
index++;
if (index == word.length())
return true;
}
``````

Btw:

``````if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == '#') continue;
``````

should change to

``````if (i < 0 || i >= board.length || j < 0 || j >= board[0].length ) continue;
``````

and

``````if (dfs(board, word, i, j, index + 1))
board[iStart][jStart] = curr;
``````

change to

``if (dfs(board, word, i, j, index))``

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