Description
Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells.
Examples
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"]Explanation:
These words can be found on the board.
Input:
board = [[1]], words = ["oath","pea","eat","rain"]Output:
[1]Explanation:
Minimal case with a single-element matrix.
Input:
board = [["c","a","t"],["o","r","s"],["d","o","g"]], words = ["cat","car","dog","cod","art","go","dots"]Output:
["cat","car","dog","cod","go"]Explanation:
This example demonstrates multiple overlapping paths: 'cat' follows c→a→t horizontally, 'car' goes c→a→r diagonally down-right then down, 'dog' follows d→o→g horizontally in bottom row, 'cod' goes c→o→d vertically down the first column, and 'go' follows g→o upward. Words 'art' and 'dots' cannot be formed from adjacent cells on this board.
Constraints
- •
m == board.length - •
n == board[i].length - •
1 ≤ m, n ≤ 12