A data-center technician is auditing a rectangular server rack laid out as a grid of m rows and n columns of cable ports. Each port is in one of three states: . means the port is free and can accept any single letter when a label is engraved, # means the port has been decommissioned and can never hold part of a label, and a lowercase letter means the port already carries that letter, engraved when an earlier cable was installed.
The technician wants to engrave a new cable label -- a string of lowercase letters -- along one unbroken straight run of ports in a single row (read left-to-right or right-to-left) or a single column (read top-to-bottom or bottom-to-top). The run used must consist entirely of ports that are not decommissioned, its length must be exactly the length of the label, and the port immediately beyond each end of the run (if such a port exists on the grid) must be decommissioned -- so the label always fills the run exactly, never spilling into or falling short of a longer stretch of usable ports. Within the run, every already-engraved port must match the label's corresponding letter in the direction chosen, while every free port may take on whatever letter the label needs there.
Determine whether at least one row-run or column-run, read in at least one of its two directions, lets the label be engraved.
Line 1: two integers m and n, the number of rows and columns.
Next m lines: each a string of exactly n characters, each character ., #, or a lowercase English letter -- the current state of the rack.
Next line: a single string w, the cable label to place.
Print YES if the label can be engraved as described, otherwise print NO.
., #, or a lowercase English letter; w consists only of lowercase English letters.Example 1
Input
3 4 #..# ..a. #..# cat
Expected
YES
Explanation
Look at column index 2 (0-based): its three ports, top to bottom, are '.', 'a', '.'. That column has no decommissioned port at all, so its usable run spans the full height of 3, exactly matching the label length of 3. Reading top-to-bottom against "cat": the free top port can take 'c', the middle port already carries 'a' which matches the label's middle letter, and the free bottom port can take 't'. Every position is satisfied, so the answer is YES.
Example 2
Input
2 3 ab# cd# xy
Expected
NO
Explanation
The only length-2 runs are row 0's "ab", row 1's "cd", column 0's "ac", and column 1's "bd" (column 2 is entirely decommissioned, giving no usable run). Checking "xy" against each, forward or reversed, always compares 'x' or 'y' against one of a, b, c, d, and none of those match. No run can host the label in either direction, so the answer is 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 →