AlphabetPath | Topcoder Archive

Problem Statement

You are given a 2-dimensional matrix of characters represented by the String[] letterMaze. The i-th character of the j-th element of letterMaze represents the character at row i and column j. Each of the 26 letters from 'A' to 'Z' appears exactly once in letterMaze, the remaining characters are periods ('.').

An alphabet path is a sequence of 26 elements of the matrix such that:

The first element contains the letter 'A'.
The first element and the second element are (horizontally or vertically) adjacent.
The second element contains the letter 'B'.
The second element and the third element are (horizontally or vertically) adjacent.
...
The 25-th element and the 26-th element are (horizontally or vertically) adjacent.
The last, 26-th element contains the letter 'Z'.

Given letterMaze return String "YES" if the alphabet path exists in the matrix and "NO" otherwise.

Definition

Class:: AlphabetPath
Method:: doesItExist
Parameters:: String[]
Returns:: String
Method signature:: String doesItExist(String[] letterMaze)
(be sure your method is public)

Notes

Formally, elements (x1,y1) and (x2,y2) are horizontally or vertically adjacent if and only if abs(x1 - x2) + abs(y1 - y2) = 1.

Constraints

letterMaze will contain between 1 and 50 elements, inclusive.
Each element of letterMaze will contain between 1 and 50 characters, inclusive.
All the elements of letterMaze will contain the same number of characters.
Each element of letterMaze will only contain uppercase letters ('A'-'Z') and periods ('.').
Each uppercase letter from 'A' to 'Z' will appear exactly once in letterMaze.

Examples

{"ABCDEFGHIJKLMNOPQRSTUVWXYZ"}

Returns: "YES"

Simply go from left to right.

{"ADEHI..Z",
 "BCFGJK.Y",
 ".PONML.X",
 ".QRSTUVW"}

Returns: "YES"

{"ACBDEFGHIJKLMNOPQRSTUVWXYZ"}

Returns: "NO"

```
{"ABC.......",
 "...DEFGHIJ",
 "TSRQPONMLK",
 "UVWXYZ...."}
```
```
Returns: "NO"
```
The cells marked with C and D are not adjacent, it is impossible to make an alphabet path in this case.

{"..............",
 "..............",
 "..............",
 "...DEFGHIJK...",
 "...C......L...",
 "...B......M...",
 "...A......N...",
 "..........O...",
 "..ZY..TSRQP...",
 "...XWVU.......",
 ".............."}

Returns: "YES"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.