Word Search II — Hard Coding Interview Question

Given an m x n board of characters and a list of words, return all words on the board.

Example

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"]

Constraints

• 1 <= m, n <= 12
• 1 <= words.length <= 3 * 10^4

Topics & Companies

Topics: trie, backtracking

Asked by: Amazon, Google, Meta

Optimal Solution Complexity

Time complexity: O(M*N * 4^L). Space complexity: O(W*L).

Practice more

• All DSA Problems
• DSA Patterns