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 uniqueboard = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]Output["oath", "eat"]WhyBoth `oath` and `eat` can be formed using adjacent horizontal or vertical moves without reusing a cell.board = [["a","b"],["c","d"]], words = ["abcb","ab","acdb"]Output["ab", "acdb"]Why`ab` is found across the top row, and `acdb` is found by traversing down, right, up. `abcb` is invalid because it would reuse a cell.1 <= board.length <= 121 <= board[0].length <= 121 <= words.length <= 3 * 10^41 <= words[i].length <= 10board[i][j] consists of lowercase English letterswords[i] consists of lowercase English lettersAll words in words are uniquedef find_words(board, words):
