212. Word Search II
Word Search II (LeetCode 212) is a Hard 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.
How to solve Word Search II
Word Search II 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:
- You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?
- If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem: <a href="https://leetcode.com/problems/implement-trie-prefix-tree/">Implement Trie (Prefix Tree)</a> first.
The reference solution runs in O(M * 4^L + N) time and O(N + L) space.
The Word Search II solution and editorial walks through the full approach with reference code.
Problem statement
Given an m x n board of characters and a list of strings words, return all words on the board.
Each word must 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 in a word.
Example 1:
Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] Output: ["eat","oath"]
Example 2:
Input: board = [["a","b"],["c","d"]], words = ["abcb"] Output: []
Constraints:
- m == board.length
- n == board[i].length
- 1 <= m, n <= 12
- board[i][j] is a lowercase English letter.
- 1 <= words.length <= 3 104
- 1 <= words[i].length <= 10
- words[i] consists of lowercase English letters.
- All the strings of words are unique.
Topics and companies
Topics: Array, String, Backtracking, Trie, Matrix.
Reported in interviews at Amazon, Microsoft, Uber, Apple, Google, Facebook, Snapchat, Twitter.
How to practise Word Search II 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 * 4^L + N) time and O(N + L) space.
Open Word Search II in the code editor, or read the Word Search II editorial for a worked solution with its approach and complexity analysis.
Where Word Search II 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 II
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 — Medium, same subpattern
- Combinations — Medium, same pattern
- Combination Sum — Medium, same pattern
- Combination Sum II — Medium, same pattern
- Generate Parentheses — Medium, same pattern
Word Search II FAQ
What is the LeetCode number of Word Search II?
Word Search II is LeetCode problem 212, rated Hard.
What pattern is used to solve Word Search II?
Word Search II 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 II?
The reference solution runs in O(M * 4^L + N) time and O(N + L) space.
Which companies ask Word Search II?
Word Search II has been reported in interviews at Amazon, Microsoft, Uber, Apple, Google, Facebook, Snapchat, Twitter.