Word Search

You are given a 2D board of characters and a list of words. Your task is to find all the words from the list that can be constructed from letters of sequentially adjacent cells in the board.

You can move in all 8 directions:

• Horizontally: left ↔ right
• Vertically: up ↕ down
• Diagonally: all 4 diagonal directions

You cannot use the same cell more than once for the same word.

---

🧪 Example

Input:

const board = [
  ['o', 'a', 'a', 'n'],
  ['e', 't', 'a', 'e'],
  ['i', 'h', 'k', 'r'],
  ['i', 'f', 'l', 'v']
];
const words = ["oath", "pea", "eat", "rain"];

Output:

["oath", "eat"]

Explanation:

• "oath" and "eat" are found in the board following valid directions.
• "pea" and "rain" are not present in any valid path.

---

✅ Constraints

• The board contains only lowercase English letters.
• The same cell may not be reused within a word path.
• The words list may contain up to 3 * 10⁴ words.
• The board dimensions can be up to 12 x 12.

---

⚠️ Edge Cases to Consider

• If the board is empty, return an empty array.
• If the words list is empty, return an empty array.
• Words may appear more than once via different paths, but should only be added once in the result.
• Words can appear diagonally as well — all 8 directions must be supported.