Loading...
Loading...
Loading...
A college fest runs a word-hunt game. The board is a grid of r rows and c columns of lowercase letters. You also get a list of w words.
A word is found if you can trace it letter by letter through cells that share a side (up, down, left or right, not diagonal). One cell can be used at most once in the same word.
Print every word from the list that can be found, in alphabetical order, one per line. Print each word only once, even if it is listed or found more than once. If no word can be found, print none.
none.Example 1
Input
3 4 sale pgat yrdc 5 gate sale tag pay cart
Output
gate sale tag
sale is the top row. gate goes g, a, t, then up to e. tag is the same path backwards. pay and cart cannot be traced.
Example 2
Input
2 2 ab cd 3 ad abdca e
Output
none
a and d do not share a side. abdca would need the cell a twice. e is not on the board.
Try the problem first. Open one hint at a time.
Searching the board once per word repeats a lot of work when many words share their first letters.
Put all the words into a letter tree first. Then start a search from every cell and walk the tree together with the board.
Stop a path as soon as the letters so far are not the start of any word in the tree.
Mark a cell as used while it is on the current path, and unmark it when you step back. When you reach the end of a word, save it and clear that mark in the tree so it is not saved again.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor