An ancient rune tablet is a grid of lowercase letters with R rows and C columns. A word can be traced on the tablet if it is possible to start at some cell and repeatedly step to a horizontally or vertically adjacent cell so that the visited cells, in order, spell the word. No cell may be used more than once within a single trace.
Determine whether the given target word can be traced on the tablet.
Line 1: two integers R and C.
Next R lines: each a string of exactly C lowercase letters (one grid row).
Last line: the target word (lowercase letters).
Print YES if the word can be traced, otherwise NO.
Example 1
Input
2 2 ab cd abdc
Expected
YES
Explanation
Start at a (0,0), step right to b (0,1), down to d (1,1), left to c (1,0): all adjacent and no reuse, so YES.
Example 2
Input
2 2 ab cd abc
Expected
NO
Explanation
After a then b, the only unused neighbor of b is d, not c, so the trace cannot continue: NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →