PayPal Word Search Grid Interview - DFS Backtracking

Problem overview

You're given an m × n letter grid (matrix) and a target word. You must determine whether the word can be formed by walking through sequentially adjacent cells (only horizontal or vertical moves). You cannot reuse the same cell within a single match.

What you'll be asked to do

You should implement a function that returns True if the target string exists in the board under those rules, otherwise False. In an online assessment you will typically be asked to: start a search from candidate start cells that match the first character, explore neighbors using DFS, and backtrack when a path fails.

High-level approach and flow

1. Validate inputs and handle edge cases (empty word, empty board, word length > m*n).
2. For each cell matching word[0], run a DFS that tries to match characters one-by-one, marking visited cells and restoring them after backtracking.
3. If DFS reaches the end of the word, return True; otherwise continue searching.

Skills and signals you should demonstrate

• Correct DFS/backtracking implementation and in-place visited marking (or boolean visited array).
• Reasoning about time and space complexity (worst-case O(mn4^L) naive; L = word length) and practical pruning.
• Handling edge cases and writing clear, testable code.

Optimizations & interview tips

• Early pruning: compare character frequencies or stop when remaining cells < remaining letters.
• In-place marking (e.g., temporary sentinel) to save memory, but restore state before returning.
• For multiple-word variants, mention Trie + DFS (Word Search II).

Practice writing the DFS iteratively and recursively, and be ready to explain trade-offs and complexity.