79. Word Search

Solving another interesting question today: Word Search. The hint suggested using Depth-First Search (DFS), but I couldn’t solve it that way. This is a problem I will definitely revisit in the future to see if I can figure it out.

I've actually come across this problem many times before, but every time I saw it, I got stuck for days and couldn't move forward. Eventually, I would give up on LeetCode altogether. Today, I finally accepted that it’s okay to look at solutions and learn from them.

Challenges I Faced

• I tend to avoid writing too many conditions in my code.
• I was too fixated on using DFS in a strict way and struggled to modify it to fit the problem.

Looking at the solutions, I noticed a pattern: they rely on multiple conditions using "or" statements:

if row < 0 or row >= len(board) or column < 0 or column >= len(board[0]) or board[row][column] != word[index]:
    return False

This checks if the current position is out of bounds or if the character does not match.

Another key part of the solution is the recursive DFS call in four directions:

if dfs(row+1, column, index+1) or dfs(row-1, column, index+1) or 
   dfs(row, column+1, index+1) or dfs(row, column-1, index+1):
    return True

This explores all possible paths until the word is found.

Lessons Learned

1. Don't hesitate to write long conditions if they are necessary for the logic.
2. It's okay to modify DFS logic instead of following it strictly.
3. Understanding base cases and recursion flow is crucial in problems like this.

Solution Breakdown

1. Check if we have reached the end of the word. If so, return True.
2. Verify if the current character matches the word and is still within bounds.
3. If the it is out of bound or character does not match, return False. Otherwise, proceed.
4. Mark the cell as visited by replacing it with an empty string.
5. Recursively search in all four directions.
6. If result is True, return True.
7. Else, if the word is not found, restore the character.
8. Start the search from each row and column.

Full Code:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # row and column is the position in the board, index is the index of the word
        def dfs(row, column, index):
            if index == len(word):  # If the index equals the length of the word, return True
                return True  # Word has been found

            # If out of bounds or character does not match
            if row < 0 or row >= len(board) or column < 0 or column >= len(board[0]) or board[row][column] != word[index]:
                return False

            temp = board[row][column]
            board[row][column] = ''  # Mark as visited

            # Check all 4 directions
            if (dfs(row+1, column, index+1) or dfs(row-1, column, index+1) or 
                dfs(row, column+1, index+1) or dfs(row, column-1, index+1)):
                return True

            board[row][column] = temp  # Restore character
            return False

        for row in range(len(board)):
            for column in range(len(board[0])):
                if dfs(row, column, 0):
                    return True

        return False

That’s all for today! I’ll keep practicing and refining my approach to DFS. Hopefully, in the future, I’ll be able to solve this problem on my own without looking at solutions.