Back to Practice Dashboard
Top 150 InterviewEasy
Word Search
Learn how to solve the 'Word Search' problem. This detailed resource details brute force and optimized approaches.
Problem Statement
Easy
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.
Implement a function exist(board: list, word: str) -> bool.
Constraints
- •m == board.length
- •n == board[i].length
- •1 <= m, n <= 6
- •1 <= word.length <= 15
- •board and word consists of only lowercase and uppercase English letters
Examples
Example 1
Input
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED"
Output
True
Explanation
The word ABCCED can be traced: A(0,0)->B(0,1)->C(0,2)->C(1,2)->E(2,2)->D(2,1).
Example 2
Input
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "SEE"
Output
True
Explanation
The word SEE can be traced: S(1,3)->E(2,3)->E(2,2).
Example 3
Input
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCB"
Output
False
Explanation
Cannot trace ABCB without reusing cells.
Need a Hint?
Analyze the input constraints. Try sorting first (O(n log n)) or using a hash map/set to track seen elements in O(n) time.
Edge Cases to Watch
- Empty list or null input variables
- Single item lists/arrays
- Extremely large input bounds causing integer or stack overflow
Ready to Solve?
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.