My Java Solution using Simple Backtracking Recursion, Time Complexity?


  • 0
    S

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

  • 1
    S

    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]


  • 0
    X

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


  • 0
    L

    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;


Log in to reply
 

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