79. Word Search

[mah-shamim]

Topics: Array, String, Backtracking, Matrix

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

• Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
• Output: true

Example 2:

• Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
• Output: true

Example 3:

• Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
• Output: false

Constraints:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

Follow-up: Could you use search pruning to make your solution faster with a larger board?

[mah-shamim]

To solve this problem, we can follow these steps:

Let's implement this solution in PHP: 79. Word Search

Explanation:

1. Initialization:

   • The exist function iterates through each cell in the grid. It starts a DFS search from each cell to see if the word can be constructed from that starting point.

2. DFS Search (dfs function):

   • Bounds Check: The DFS function first checks if the current position is out of bounds or if the character at the current position doesn't match the current character in the word.
   • Word Completion: If the current character matches and the end of the word is reached, it returns true.
   • Marking Cells: It marks the current cell as visited by setting it to '*' to avoid reusing the same cell.
   • Recursive Exploration: It recursively searches in the four possible directions (up, down, left, right).
   • Unmarking Cells: After exploring all directions, it restores the original character in the board.

This approach ensures that each cell is visited at most once per search and uses backtracking to ensure the solution remains efficient.

[basharul-siddike]

Thanks for solving the problem of "Word Search"

[mah-shamim]

Thanks