Word search II
HardStuck?
Show a hintHide the hint
Put the words in a trie and walk the grid once. A branch with no matching child in the trie cannot spell any word, so it stops immediately.
The ideas behind this problem
Next in this lesson
Every subset, in orderGiven a grid of lowercase letters and a list of words, return every word that can be formed by walking through adjacent cells.
Cells are adjacent horizontally or vertically, and a cell may not be reused within a single word. Searching each word separately is too slow: build a trie of the words and walk the grid once.
Constraints#
1 <= rows, cols <= 121 <= words <= 3000- Words are lowercase and at most 10 characters.
Input
board is a row count then that many rows of letters. words is a count then that many words.
Output
The matching words, in the order they were given, one per line. Print nothing if none match.
Examples
Input
2 ab cd 2 abcd acdb
Output
acdb
`acdb` walks a to c to d to b through adjacent cells. `abcd` would need b and c to be adjacent, and they are not.
Input
1 abc 2 abc cba
Output
abc cba
A row can be walked either way, so both words are found.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.