Meta wants to scan a character grid for valid keywords that may appear in surfaces like Messenger game boards. Given a 2D board of lowercase letters and a list of lowercase words, return all words that can be formed by traversing adjacent cells.
A word can be constructed from letters of sequentially adjacent cells, where adjacency is horizontal or vertical. The same cell may not be used more than once in a single word.
Implement a function that takes:
board: a list of m rows, each row a list of n lowercase characterswords: a list of distinct lowercase stringsReturn a list of all words from words that appear in the board. The output may be in any order.
Example 1
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]["oath", "eat"]oath and eat can be formed by valid paths; pea and rain cannot.Example 2
board = [["a","b"],["c","d"]], words = ["abcb","ab","acdb"]["ab", "acdb"]abcb is invalid because it would require reusing cell b.1 <= m, n <= 121 <= words.length <= 3 * 10^41 <= words[i].length <= 10board[i][j] and words[i][k] are lowercase English letterswords are unique