Word Search II

Word Search II 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.

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), where M = number of cells in the board, L = max word length, N = total number of characters in all words. Trie construction is O(N), and DFS is pruned by the Trie, so total search is proportional to the number of valid paths. time and O(N + L), where N = total number of characters in all words (Trie size), and L = max depth of recursion (max word length). The board is modified in-place, so no extra visited array is needed. 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
• All coding practice problems

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