PROBLEM STATEMENT
A crossword puzzle contains words placed horizontally or vertically. Two
letters may be adjacent only if they are part of the same word, but vertical
and horizontal words may cross each other at a shared letter. In fact, we
require that every word in a crossword puzzle cross at least one other word.
The "size" of a crossword puzzle is the larger of the horizontal and vertical
dimensions of the smallest rectangle that contains the puzzle.
Create a class Crossword that contains the method smallest that takes 3 words
as input and returns the smallest possible size for a puzzle that contains just
those words. If no crossword puzzle can be constructed from the 3 words, return
-1.
DEFINITION
Class: Crossword
Method: smallest
Parameters: String[]
Returns: int
Method Signature (be sure your method is public): int smallest(String[]
threeWords);
NOTES
- return -1 if it is not possible to construct a crossword puzzle from threeWords
- two vertical words cannot share a letter, nor can two horizontal words share
a letter
- horizontal words must go from left to right, vertical words must go from top
to bottom
- letters from two different words are allowed to be diagonally adjacent
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- threeWords contains exactly 3 elements
- each element of threeWords contains only uppercase letters A-Z
- each element of threeWords contains between 2 and 20 letters inclusive
EXAMPLES
(quotes shown for clarity only)
1) {"ABC","CARD","LIMB"}: return 7
A
LIMB
CARD
is the only legal puzzle (except for rotation). It is 3 high but 7 wide. Its
size is the bigger of those two numbers.
2) {"AAA","AAA","AAA"}: return 3
A A
AAA
A A
(there are others that have size 3, size 4, and size 5)
3) {"GO","TO","BED"}: return -1
there is no way to connect BED to either of the other words
4) {"BIRDS","CHOIR","BANANA"}: return 10
BANANA
I
CHOIR
D
S
note that crossing CHOIR and BIRDS at the I would make the size smaller, but is
illegal because the R of CHOIR would then be adjacent to the first A in BANANA.