Shortest Route in a Character Matrix
Filed under Accolite
Free read 3 of 3Confirm if cells can be revisited or if movement is strictly non-overlapping.
The question
Given a 2D grid of characters and a target word, find and print the shortest path instructions (move left, right, up, down) across the matrix starting from a specific index to spell the word.
Constraints
- Grid dimensions are within reasonable limits (e.g., up to 50x50).
- Target word consists of uppercase English letters.
Examples
- Input
- grid = [['A', 'C'], ['L', 'O']], start = (0,0), word = 'AC'
- Output
- ["RIGHT"]
- Why
- Start at (0,0) 'A' and move right to (0,1) 'C'.
Approach
Confirm if cells can be revisited or if movement is strictly non-overlapping.
Explore all possible paths using DFS/BFS from the starting index matching the word characters sequentially.
Use Backtracking DFS with path recording. Track visited coordinates to prevent infinite loops, and store the shortest sequence of directions.
Start cell does not match the first letter of the word, or word cannot be formed.
Tips
- What they are testing: Test with words that require backtracking, revisiting cells, or dead ends.
- Common mistake: Forgetting to unmark visited cells during backtracking when searching for paths in a grid.
Related Accolite questions
Collected from public candidate posts and coding forums. Updated Nov 2026.