Word Search II
Hard · Tries · Array · String · Backtracking · Trie · Matrix
Problem
Given an m × n board of lowercase letters and a list of words, return every word from the list that can be traced on the board.
The tracing rules are those of Word Search: a trace starts on any cell, steps up, down, left or right, and the letters it visits spell the word. No cell is used twice within one word, although different words may use the same cells.
Return the words in any order, each one once: a word counts once even if it can be traced along several paths, or appears in words more than once. (On LeetCode the words are all different; here they may repeat.)
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"]
oath starts at the top-left o, and eat at the e at the right end of the second row. There is no p on the board, and no a next to the r, so pea and rain fail.
Input: board = [["a","b"],["c","d"]], words = ["abcb"] Output: []
The word needs the b twice, and there is only one b cell.
Constraints
- m == len(board), n == len(board[i])
- 1 <= m, n <= 12
- board[i][j] is a lowercase English letter
- 1 <= len(words) <= 3 * 10^4
- 1 <= len(words[i]) <= 10, lowercase English letters
- words may contain the same word more than once (on LeetCode they are unique)
Approaches
- Word Search once per word — time O(w · m · n · 3^L), space O(L)
Related problems
Start free on Cariara · Coding problems · System design studio
