Find all dictionary words in a letter grid
Coding problemHardAsked in: Airbnb, Amazon, Apple, Google, Meta, Uber
You are given a grid of lower case letters, one string per row, and a list of distinct words. Return every word from the list that can be traced in the grid.
A word is traced as in a word search: start on a cell holding its first letter and step to a neighbouring cell (up, down, left or right) for each next letter. A cell can be used at most once within the same word, but different words may use the same cells. Return each found word once, in any order.
Examples
Example 1
Input: grid = ["oaan","etae","ihkr","iflv"], words = ["oath","pea","eat","rain"]
Output: ["oath","eat"]
Example 2
Input: grid = ["ab","cd"], words = ["abdc","abcd","ca"]
Output: ["abdc","ca"]
Example 3
Input: grid = ["a"], words = ["a","aa"]
Output: ["a"]
Constraints
- The grid has between 1 and 12 rows and between 1 and 12 columns; all rows have the same length
- The list holds between 1 and 1,000 distinct words of 1 to 10 letters
- Only lower case English letters appear
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.