Facebook Pixel

Word Search II

You are given a 2-D matrix of lowercase characters and a list of words. Starting from any cell, you may move to an adjacent cell (up, down, left, or right) without reusing a cell already on the current path. A word is found when its letters can be spelled by such a path.

Return every word in words that can be built this way, in the exact order it appears in the list. The matrix input is given as a list of strings, one per row.

Click a word to trace its path through adjacent cells. Words with no valid path are reported as not found.

NOTE: test case 7 might be hard to handle for slower languages such as Javascript and Python in which case you should skip the case. Solutions written in faster compiled languages such as Java and C++ should aim to pass the case.

Input & Output
Input
matrix — list of strings representing the 2-d matrix of characters
words — list of words to check if they can be made
Output
list of all possible words that can be made
Example
Input
matrix = [aab, aaa]
words = [bb, aa, abaa]
Output
[aa, abaa]
Explanation

We can easily make aa by starting at any of the cells containing a in the matrix then moving to another cell containing a. We cannot make bb as once we start at the 1 b position there is no other b to move onto to make bb.

Constraints
  • 1 <= (row of matrix) * (column of matrix) <= 100
  • Each character will be a lower case english letter
  • 1 <= words.length <= 30001
  • 1 <= words[i].length <= 10

Try it yourself

Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro