633. Find All Words
You are given a rectangular board of lowercase letters and a list of words. A word is on the board if it can be spelled by walking from tile to tile, where each step moves to a tile directly above, below, left or right of the previous one, and no tile is used twice within the same word.
Return every word from words that is on the board. Each such word must appear exactly once in the answer, even if it is listed several times in words. The words may be returned in any order.
Example 1
- Input:
- board = [["c","a","r"],["o","t","e"],["s","t","a"]]words = ["cat","care","core","cost","tea","rat","cart","oats","star","tar","ace"]
- Output:
- ["cost","cat","care","rat","tar","tea"]
- Explanation:
Six words can be traced:
cost(c, down to o and s, then right to t),cat,care,rat,tarandtea. The others would need a tile twice or two tiles that are not neighbours.
Example 2
- Input:
- board = [["a","b"],["b","a"]]words = ["ab","ba","aba","abba","aa","bb"]
- Output:
- ["ab","aba","ba"]
- Explanation:
ab,baandabacan be walked.abbawould need the twobtiles to be neighbours, but they sit diagonally.
Example 3
- Input:
- board = [["z"]], words = ["z","zz","a"]
- Output:
- ["z"]
- Explanation:
Only the single tile
zexists, so just the wordzfits.
Constraints
- 1 ≤ number of rows, number of columns ≤ 10
- 1 ≤
words.length≤ 100 - 1 ≤
words[i].length≤ 10 - The board and the words contain only lowercase English letters.
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
Expected complexity
- Time
- O(R * C * 3^L) in the worst case
- Space
- O(total length of all words)