Word Search II
HardTries
You are given an m x n grid of lowercase letters board and a list of distinct strings words. Return every word from words that can be spelled by a path through the grid.
A path:
- starts at any cell and moves one step at a time up, down, left or right (no diagonals),
- spells the word letter by letter, in order,
- may not use the same cell more than once within that word (different words may reuse cells).
Include each found word once, even if it can be traced in several ways. The result may be in any order. Return an empty list if no word can be traced.
Example 1
- Input:
- board = [["o","a"],["e","t"]], words = ["oat","tea","eat","toe"]
- Output:
- ["oat"]
- Explanation
- Only one word can be traced through neighbouring cells. The others each need a diagonal step at some point.
Example 2
- Input:
- board = [["c","a","t"],["x","r","s"]], words = ["cat","car","cart","cars","rat","star"]
- Output:
- ["car","cars","cat","rat","star"]
- Explanation
cat,car,cars(c → a → r → s),ratandstar(s → t → a → r) can all be traced.cartcannot, because notsits next to ther.
Example 3
- Input:
- board = [["a","b"],["b","a"]], words = ["abab","aba","baa","abba"]
- Output:
- ["aba","abab"]
- Explanation
ababwalks around the whole board: (0,0) → (0,1) → (1,1) → (1,0), andabais the first three steps of that walk.baaandabbawould need two equal letters side by side, but the twoas and the twobs are each diagonal to each other.
Constraints
m == board.length,n == board[i].length1 <= m, n <= 12board[i][j]is a lowercase English letter1 <= words.length <= 3 * 10^41 <= words[i].length <= 10words[i]consists of lowercase English letters, and all strings inwordsare distinct