Problem · Trie
Word Search II
Learn this problemProblem statement
Given an m x n board of lowercase English letters and an array of distinct lowercase words, return every word that can be formed on the board.
A word is formed by starting at any cell and repeatedly moving one cell horizontally or vertically. A board cell may be used at most once while forming a word.
Return the found words in the same order in which they appear in words.
Function
findWords(board: char[][], words: String[]) → String[]Examples
Example 1
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]words = ["oath","pea","eat","rain"]return = ["oath","eat"]The paths o-a-t-h and e-a-t use horizontal or vertical neighbors without reusing a cell. The other two words cannot be formed.
Example 2
board = [["a","b"],["c","d"]]words = ["abcb","abcd","acdb"]return = ["acdb"]acdb follows the path down, right, then up. Forming abcb would require reusing the b cell, and abcd would require a diagonal move.
Example 3
board = [["a"]]words = ["a","b"]return = ["a"]The one-cell board forms a but not b.
Constraints
1 <= m, n <= 121 <= words.length <= 300001 <= words[i].length <= 10- The board and every word contain only lowercase English letters.
- All words are distinct.