Learning Journal

2/13/2024

Word Search - 3rd 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(check(row, col, 0)) return true;  
   }

   return  false;


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

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

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


        board[row][col] = word[iW];
       
        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(check(row, col, 0)) return true;  
   }

   return  false;


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

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

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


        board[row][col] = word[iW];
       
        return false;
   }

};

THE PROBLEM

This time, I just realized some nuances of this approach.

First, why do you need to unmark the current cell when you know that it is not the path you're looking for before you return false? Because if you don't, the algorithm, while going other directions, and because it checks 4 directions, might come back to the cells that you visited during the last check, making a circle.

Secondly, why do you stop when you call check on one direction and it returns true but not false? It is because if the current direction is the right path, you do not need to check anymore. You only need to find one result, not all of the results. But if it's false, you need to check all four directions. And only after all four directions return false, you are sure that there's nothing you can do about that direction anymore, thus, you return false.

Revised by ChatGPT

Upon further reflection, I've noticed some intricate aspects of this approach.

Firstly, the necessity of resetting the current cell ("unmarking") after determining it's not part of the desired path arises from the algorithm's nature of exploring in four directions. Without resetting as the search continues in other directions, it might inadvertently loop back to cells previously visited in an unsuccessful attempt thereby creating a cycle and potentially overlooking valid paths.

Secondly, the reason for halting the exploration upon a successful check call in any direction (when it returns true) is that finding just one valid path suffices for the task at hand; there's no need to discover every possible route. Conversely, if a check call returns false, it's essential to exhaust all four directions before concluding that the current path is a dead end. This ensures that the algorithm only declares failure to find a path after all possible exploratory routes have been considered and found wanting.

This nuanced approach optimizes the search process, ensuring efficiency and accuracy in determining the presence of the specified word within the board.