MediumBacktrackingAI interview only
Word Search
Asked atamazonmetamicrosoftbloomberggoogleappleoracle
01 · Problem
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
02 · Examples
Example 01
Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output
true
The path A→B→C→C→E→D traces through adjacent cells without reusing any cell.
Example 02
Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output
true
Starting from S at position (1,3), moving down to E at (2,3), then left to E at (2,2).
Example 03
Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output
false
Cannot form ABCB because the B at (0,1) would need to be visited twice.
03 · Constraints
- 01m == board.length
- 02n == board[i].length
- 031 <= m, n <= 6
- 041 <= word.length <= 15
- 05board and word consist of only lowercase and uppercase English letters
04 · Optimal complexity
- Time
- O(m * n * 4^L)
- Space
- O(L)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.