Implement 2D word search variants and analyze complexity
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an m x n grid of uppercase letters board and a string word, implement two related functions:
(
1) Fixed-direction search: Return true if word appears by choosing any start cell and moving in exactly one of eight directions (N, NE, E, SE, S, SW, W, NW), advancing one cell per step without changing direction or leaving bounds. Analyze time and space complexity, and explain how to avoid redundant checks.
(
2) Flexible-path search: Return true if word can be formed by starting at any cell and moving to one of four orthogonal neighbors (up, down, left, right) at each step; you may change direction between steps but may not reuse a cell within a single path. Describe your algorithm (e.g., DFS/backtracking with pruning), its complexity, and key differences versus the fixed-direction variant. Specify how you would handle edge cases such as empty word, single-character inputs, repeated letters, and large grids.
Quick Answer: This question evaluates proficiency in grid-based string search, traversal techniques (fixed-direction scanning versus flexible-path exploration), algorithm design including backtracking/DFS, and the ability to analyze time and space complexity while accounting for redundancy and edge cases.
Fixed-Direction Word Search (8 Directions)
Given an m x n grid of uppercase letters `board` and a string `word`, return `true` if `word` appears by choosing any start cell and moving in exactly one of the eight directions (N, NE, E, SE, S, SW, W, NW), advancing one cell per step WITHOUT changing direction and without leaving the grid bounds.
Unlike the classic LeetCode "Word Search", the path here is a straight ray: once you pick a starting cell and one of the 8 directions, every subsequent character must lie on that same straight line. You may not turn, and a cell is never revisited (a straight ray of distinct cells never repeats one anyway).
Return `false` if no such straight-line placement exists.
Examples:
- board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "AFE" -> true (A at (0,0), F at (1,1), E at (2,2): the SE diagonal).
- board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE" -> false (no single straight 8-direction ray spells SEE).
Edge cases to handle: empty word (return true vacuously), single-character word, empty board, and repeated letters.
Constraints
- 1 <= m, n <= 200 (board may also be empty in edge cases)
- 0 <= len(word)
- board[i][j] and word are uppercase English letters
Examples
Input: ([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABC')
Expected Output: True
Explanation: A(0,0) -> B(0,1) -> C(0,2) is a straight Eastward ray.
Input: ([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'SEE')
Expected Output: False
Explanation: No single 8-direction straight ray spells SEE; turning is not allowed.
Hints
- There are exactly 8 direction vectors: (-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1). Iterate over them as a fixed list.
- Before walking a ray, compute the end cell start + dir*(L-1); if it is out of bounds, skip that direction entirely (cheap bounds prune).
- Only begin a ray from a cell matching word[0]; break the inner scan on the first mismatch.
Flexible-Path Word Search (4-Neighbor Backtracking)
Given an m x n grid of uppercase letters `board` and a string `word`, return `true` if `word` can be formed by starting at any cell and moving to one of the four orthogonal neighbors (up, down, left, right) at each step. You MAY change direction between steps, but you may NOT reuse the same cell within a single path. This is the classic LeetCode 79 "Word Search".
Use DFS / backtracking: from each starting cell that matches word[0], recursively try the 4 neighbors for the next character, temporarily marking the current cell as visited (e.g. overwrite with a sentinel like '#') and restoring it on the way back.
Return `false` if no path spells the word.
Examples:
- board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED" -> true.
- board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE" -> true.
- board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB" -> false (would require reusing the B cell).
Key differences vs. the fixed-direction variant: this path may turn at every step and is constrained only by the no-reuse rule, so the search space is exponential rather than linear. Edge cases: empty word (true), single character, repeated letters (the no-reuse rule matters), and empty board.
Constraints
- 1 <= m, n <= 200 (board may also be empty in edge cases)
- 0 <= len(word)
- board[i][j] and word are uppercase English letters
- A cell may not be reused within a single path
Examples
Input: ([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABCCED')
Expected Output: True
Explanation: A(0,0)->B(0,1)->C(0,2)->C(1,2)->E(2,2)->D(2,1), turning as needed.
Input: ([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'SEE')
Expected Output: True
Explanation: S(1,3)->E(2,3)->E(2,2).
Hints
- Start a DFS from every cell whose letter equals word[0]; return true as soon as any start succeeds.
- Mark the current cell visited before recursing (e.g. set it to '#') and restore it afterward so other paths can use it (backtracking).
- Prune early: if the current cell does not match word[i], stop immediately. An optional global frequency check (does the board even contain enough of each letter?) speeds up rejections on large grids.