Word Search (Trie & Backtracking)

To solve the Word Search problem efficiently, I would treat the 2D board as an implicit graph where each cell represents a node connected to its adjacent neighbors. My approach starts by iterating through every cell in the grid to find potential starting points that match the first character of the target word. Once a match is found, I initiate a depth-first search using recursion. During this traversal, I maintain a visited set to mark the current path, ensuring we do not revisit cells within the same word construction, which prevents infinite loops. Crucially, before exploring neighbors, I check if the current cell matches the expected character at the current index; if not, I prune that branch immediately. This pruning technique is vital because it avoids unnecessary computation on dead-end paths, significantly reducing the search space. After exploring all valid directions from a cell, I must backtrack by unmarking the cell as visited so it can be part of a different word path starting elsewhere. This ensures the solution remains correct while optimizing for speed. For example, if the board is [['A','B'],['C','D']] and the word is 'AB', we start at (0,0), move to (0,1), find the match, and return true. If the word was 'ABC', we would explore 'B', fail to find 'C' in neighbors, backtrack, and stop. This method balances clarity with performance, aligning well with Uber's focus on scalable, efficient algorithms for real-world logistics.