AlgoLounge

Word Search II

hard

Leetcode 212. Word Search II

Given a 2-D grid of characters `board` and a list of strings `words`, return all words that are present in the grid.

For a word to be present it must be possible to form the word with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.

Examples

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

  • `1 <= board.length, board[i].length <= 12`
  • `board[i]` consists only of lowercase English letter.
  • `1 <= words.length <= 30,000`
  • `1 <= words[i].length <= 10`
  • `words[i]` consists only of lowercase English letters.
  • All strings within `words` are distinct.
TypeScript
Loading editor…
List of test cases (10)
Case 1
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
words = ["oath","pea","eat","rain"]
Case 2
board = [["a","b"],["c","d"]]
words = ["abcb"]
Case 3
board = [["a","a"]]
words = ["aaa"]
Case 4
board = [["a"]]
words = ["a"]
Case 5
board = [["a","b"],["c","d"]]
words = ["ab","cb","ad","bd","ac","ca","da","bc","db","adcb","dabc"]
Case 6
board = [["o","a","b","n"],["o","t","a","e"],["a","h","k","r"],["a","f","l","v"]]
words = ["oa","oaa"]
Case 7
board = [["a","a","a"],["a","a","a"],["a","a","a"]]
words = ["aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa"]
Case 8
board = [["a","b","c"],["a","e","d"],["a","f","g"]]
words = ["abcdefg","gfedcbaaa","eaabcdgfa","befa","dgc","ade"]
Case 9
board = [["m","b","c","d"],["a","a","a","a"],["a","a","a","a"],["a","a","a","a"]]
words = ["aaaaaaaaaaaaaa"]
Case 10
board = [["a","b"],["a","a"]]
words = ["aba","baa","bab","aaab","aaa","aaaa","aaba"]