Practice/Uber/Leetcode 79. Word Search

Leetcode 79. Word Search

CodingMust

Problem

You are given a 2D grid of characters and a target word string. Your task is to determine whether the word can be constructed by following a path through adjacent cells in the grid. Adjacent cells are those connected horizontally or vertically (diagonal connections do not count). Each cell in the grid can only be used once per search path.

Return true if such a path exists, otherwise return false.

Requirements

1. The search must start from any cell in the grid that matches the first character of the word
2. Each subsequent character must be found in a cell adjacent (up, down, left, right) to the previous cell
3. A cell cannot be revisited within the same path
4. The entire word must be matched character by character

Constraints

• m == board.length (number of rows)
• n == board[i].length (number of columns)
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consist of only lowercase and uppercase English letters
• Expected time complexity: O(m * n * 4^L) where L is the length of the word
• Expected space complexity: O(L) for the recursion stack

Examples

Example 1:

Input: board = [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], word = "ABCCED" Output: true Explanation: Starting from A at (0,0), we can trace the path A→B→C→C→E→D

Example 2:

Input: board = [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], word = "SEE" Output: true Explanation: Starting from S at (1,0), we can trace the path S→E→E

Example 3:

Input: board = [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], word = "ABCB" Output: false Explanation: No valid path exists because we would need to reuse cell B