All problems

Word Search II

Hard · trie

You are given a grid of lowercase letters, board, and a list of distinct strings, words. A word can be traced in the grid if its letters can be read by starting on any cell and moving one step at a time to a cell that shares an edge with the current one (up, down, left or right, never diagonally). A single trace may use each cell at most once, but different words are free to use the same cells.

Return every word from words that can be traced, sorted in alphabetical order. Each word appears at most once in the result. If no word can be traced, return an empty list.

Examples

Example 1

Input: board = [["c","a","t"], ["o","r","s"], ["d","e","n"]], words = ["cat", "cats", "core", "code", "rat", "sand", "scat"]

Output: ["cat", "cats", "code", "core", "rat"]

"cats" goes along the top row and then down to the s. "core" and "code" both start at the c and go down through the o, then to r or d. There is no a next to an s, so "sand" and "scat" cannot be traced.

Example 2

Input: board = [["a","b"], ["c","d"]], words = ["acdb", "abdc", "aa", "bad"]

Output: ["abdc", "acdb"]

"aa" would need the only a twice, and in "bad" the a and the d touch only diagonally.

Example 3

Input: board = [["a","b"], ["c","d"]], words = ["ad", "bc"]

Output: []

In both words the two letters sit on diagonal cells, so neither word can be traced.

Constraints