Learning Journal

2/12/2024

Word Search - 2nd attempt

function exist(board: string[][], word: string): boolean {

   for(let row = 0; row < board.length; row++) {
       for(let col = 0; col < board[row].length; col++) {
           if(backtrack(row,col, 0))
            return true
       }
   }

   return false;


   function backtrack(row: number, col: number, iWord: number):boolean {
       if(iWord === word.length) return true;
       else if(row < 0 || row >= board.length || col < 0 || col >= board[0].length ||
           board[row][col] !== word[iWord]) 
           return false;

       const LEFT = [0, -1], RIGHT = [0, 1], 
                UP = [-1, 0], DOWN = [1, 0],
                directions = [UP,DOWN, LEFT, RIGHT];
        board[row][col] = "#";

        for(let i = 0; i < directions.length; i++) {
            
            if(backtrack(row + directions[i][0], col + directions[i][1], iWord +1))
                return true;
        }

        board[row][col] = word[iWord];

        return false;
   }

};function exist(board: string[][], word: string): boolean {

   for(let row = 0; row < board.length; row++) {
       for(let col = 0; col < board[row].length; col++) {
           if(backtrack(row,col, 0))
            return true
       }
   }

   return false;


   function backtrack(row: number, col: number, iWord: number):boolean {
       if(iWord === word.length) return true;
       else if(row < 0 || row >= board.length || col < 0 || col >= board[0].length ||
           board[row][col] !== word[iWord]) 
           return false;

       const LEFT = [0, -1], RIGHT = [0, 1], 
                UP = [-1, 0], DOWN = [1, 0],
                directions = [UP,DOWN, LEFT, RIGHT];
        board[row][col] = "#";

        for(let i = 0; i < directions.length; i++) {
            
            if(backtrack(row + directions[i][0], col + directions[i][1], iWord +1))
                return true;
        }

        board[row][col] = word[iWord];

        return false;
   }

};

THE PROBLEM

This is my second attempt at solving this problem. Let me try to explain again how it works.

This is the backtracking approach to the problem. The backtracking algorithm works like this. You recursively go over one direction while marking your way, then when you reach the base case, depending on what the challenge asks, you will collect the result or just return a boolean value signify that you found or not found the result. Then, you go back one step, unmark the latest step and consider the next case.

This strategy likes you consider all possibilities in a clever way and return the result.

Revised by ChatGPT

This is my second attempt at solving the "Word Search" problem using a backtracking strategy. Let me explain how it works more clearly.

The backtracking algorithm navigates through the board by exploring one direction at a time, marking the path as it proceeds. Once it reaches the base case - either finding the word or exhausting all possibilities - it returns a boolean value indicating whether the word has been found. If the current path does not lead to the solution, the algorithm backtracks by unmarking the last step and exploring the next possible direction.

This approach methodically considers all potential solutions in an efficient manner, returning the final result based on whether the word exists on the board.