Word Search II Problem

Word Search II Problem — ExecCode Hard DSA Practice

Solve the Word Search II problem on ExecCode. Free online hard DSA practice in Arrays - Basics. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Given an m x n grid of characters and a list of words, return all words that can be formed by a path of adjacent cells (up, down, left, right), using each cell at most once per word. Build a trie from the word list so a single depth-first search over the board can look up multiple words at once instead of repeating a fresh search per word.

Examples

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"]. Input board = [["a", "b"], ["c", "d"]], words = ["ab", "cd", "ac", "db", "adcb"]; Output ["ab", "ac", "cd", "db"]. Input board = [["a"]], words = ["a", "b"]; Output ["a"]

Constraints

1 <= board length, board[i] length <= 12 1 <= words.length <= 3 * 10^4 1 <= words[i].length <= 10 All inputs consist of lowercase English letters

Practice Word Search II free on ExecCode. Browse DSA problems, topic map, and placement guides.