79. Word Search
Word Search (LeetCode 79) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the Word Search / Path Finding in Grid subpattern.
- Blind 75 · #38 of 75 · Backtracking
- NeetCode 150 · #73 of 150 · Backtracking
- NeetCode 250 · #131 of 250 · Backtracking
How to solve Word Search
Word Search is a Word Search and Path Finding in Grid problem, part of Backtracking Patterns. Search for words in grid using backtracking. Handle visited cells and path restoration.
Work towards the solution in these steps:
- Consider using a backtracking approach to explore possible paths in the grid that could form the given word.
- Start your search from cells that match the first character of the word and explore adjacent cells recursively to match subsequent characters.
- Keep track of visited cells to avoid reusing the same letter cell multiple times in the current search path.
The reference solution runs in O(m * n * 4^L) time and O(m * n + L) space.
The Word Search solution and editorial walks through the full approach with reference code.
Problem statement
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.
Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true
Example 2:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true
Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false
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.
Follow up: Could you use search pruning to make your solution faster with a larger board?
Topics and companies
Topics: Array, String, Backtracking, Depth-First Search, Matrix.
Reported in interviews at Amazon, Bloomberg, Intuit, Microsoft, Facebook, Snapchat, Apple, Oracle, eBay, Pinterest, Expedia.
How to practise Word Search on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n * 4^L) time and O(m * n + L) space.
Open Word Search in the code editor, or read the Word Search editorial for a worked solution with its approach and complexity analysis.
Where Word Search sits in the DSA pattern sheet
- Backtracking Patterns pattern guide
- Word Search / Path Finding in Grid subpattern
- The full DSA patterns sheet
Problems related to Word Search
Other problems that use the same Word Search / Path Finding in Grid and Backtracking Patterns techniques:
- Check if Word Can Be Placed In Crossword — Medium, same subpattern
- Word Search II — Hard, same subpattern
- Combinations — Medium, same pattern
- Combination Sum — Medium, same pattern
- Combination Sum II — Medium, same pattern
- Generate Parentheses — Medium, same pattern
Word Search FAQ
What is the LeetCode number of Word Search?
Word Search is LeetCode problem 79, rated Medium.
What pattern is used to solve Word Search?
Word Search is a Word Search and Path Finding in Grid problem. It belongs to the Backtracking Patterns pattern, in the Word Search / Path Finding in Grid subpattern.
What is the time complexity of Word Search?
The reference solution runs in O(m * n * 4^L) time and O(m * n + L) space.
Which companies ask Word Search?
Word Search has been reported in interviews at Amazon, Bloomberg, Intuit, Microsoft, Facebook, Snapchat, Apple, Oracle, eBay, Pinterest, Expedia.