# My Java Solution using Simple Backtracking Recursion, Time Complexity?

• Can anyone tell me the time complexity for this? I implemented this solution and passed the test but not really sure the time complexity.

``````public class Solution {
int width;
int height;
boolean [][] isUsed;
public boolean exist(char[][] board, String word) {
if (word.length() == 0) return true;
height = board.length;
if (height == 0) return false;
width = board[0].length;
if (width == 0) return false;

char letter = word.charAt(0);

for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
if (board[i][j] == letter) {
isUsed = new boolean[height][width];
if (isExist(board, word.substring(1), i, j, isUsed)) return true;
}
}
}
return false;
}
public boolean isExist(char[][]board, String word, int i, int j, boolean[][] isUsed) {
// base case
if (word.length() == 0) return true;
char letter = word.charAt(0);
isUsed[i][j] = true;
boolean found = false;

// for up, down, left, and right
int[] casesForY = {i-1, i+1, i, i};
int[] casesForX = {j, j, j-1, j+1};

for (int k = 0; k < 4; k++) {
int targetY = casesForY[k];
int targetX = casesForX[k];
if (canVisit(i, j, targetY, targetX, isUsed, letter, board)) {
found = isExist(board, word.substring(1), targetY, targetX, isUsed);
isUsed[targetY][targetX] = false;
if (found) return found;
}
}
return found;
}
public boolean canVisit(int myY, int myX, int targetY, int targetX, boolean [][]isUsed, char letter, char[][] board) {
if (myY == 0 && targetY < myY) return false; // where i = 0 and up case
if (myY == height-1 && targetY > myY) return false; // where i = last row and down case
if (myX == 0 && targetX < myX) return false; // where j = 0 and left case
if (myX == width-1 && targetX > myX) return false; // where j = last column and right case

if (isUsed[targetY][targetX]) return false; // target cell is already visited
if (board[targetY][targetX] != letter) return false; // target cell's letter is not what we are looking for.

return true;
}
}``````

• Have you tried creating the isUsed[][] array once? Currently it's being recreated for each match. That seems to have done the trick for me.

Also you're resetting isUsed to false for some cases but not all. It would be clearer to set `isUsed[i][j]=true` at the start of isExist, like you're currently doing, and `isUsed[i][j]=false` before returning, rather than `isUsed[targetY][targetX]`

• Have the same problem here and thanks to @sebzz, your solution works!

• In java, I think in each row, the number of the element does not need to be same. Thus, I think there might have some bugs in your code:
width = board[0].length;
if (width == 0) return false;

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