Word search in a letter grid
Coding problemMediumAsked in: Amazon, Apple, Intuit, Microsoft, NPCI
You are given a grid of letters, one string per row, and a word. Return true if the word can be traced in the grid, and false otherwise.
To trace a word, start on a cell holding its first letter, then step to a neighbouring cell (up, down, left or right, never diagonal) holding the next letter, and so on. A cell can be used at most once in the same word. Upper and lower case letters are different.
Examples
Example 1
Input: grid = ["ABCE","SFCS","ADEE"], word = "ABCCED"
Output: true
Example 2
Input: grid = ["ABCE","SFCS","ADEE"], word = "SEE"
Output: true
Example 3
Input: grid = ["ABCE","SFCS","ADEE"], word = "ABCB"
Output: false
The path would need to use the B cell twice.
Constraints
- The grid has between 1 and 6 rows and between 1 and 6 columns; all rows have the same length
- The word has between 1 and 15 letters
- The grid and the word hold upper and lower case English letters only
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.