Connection Status:
Competition Arena > SimplestCrossword

SimplestCrossword

SRM 793 · 2020-11-03 · by misof

SRM 793 · 2020-11-03 · by misof · Brute Force, String Manipulation
Class Name: SimplestCrossword
Return Type: String[]
Method Name: construct
Arg Types: (string, string)
Problem Statement

Problem Statement

You are given two Strings: H and V. Build the simplest possible crossword that contains these two strings and nothing else. H must appear horizontally, V must appear vertically, and the two strings must overlap somewhere. The crossword must be rectangular and it must be as small as possible.

Return the crossword as a String[], using '.' for cells that do not contain a letter. If there are multiple valid solutions, you may return any one of them. If there is no valid solution, return an empty String[] instead.

Constraints

  • H will contain between 2 and 10 characters, inclusive.
  • V will contain between 2 and 10 characters, inclusive.
  • Each character in H and V will be an uppercase English letter ('A'-'Z').
Examples
0)
"TOP"
"CODER"
Returns: {".C.", "TOP", ".D.", ".E.", ".R." }

This is what the return value looks like when formatted into a rectangle: {".C.", "TOP", ".D.", ".E.", ".R." } This return value describes the following crossword: .C. TOP .D. .E. .R. In this particular test case, this is the only valid solution.

1)
"CODER"
"TOP"
Returns: {".T...", "CODER", ".P..." }

Here we swapped the two words, so now CODER should go horizontally. The returned crossword looks as follows: .T... CODER .P...

2)
"AAAAA"
"AAAAAA"
Returns: {"...A.", "...A.", "...A.", "AAAAA", "...A.", "...A." }

Returned crossword: ...A. ...A. ...A. AAAAA ...A. ...A. In this case there are 29 other valid crosswords, and each of those would be accepted as well.

3)
"CAT"
"DOG"
Returns: { }

We cannot make these two words overlap.

4)
"FZUHE"
"DYVBX"
Returns: { }

Submissions are judged against all 96 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SimplestCrossword with a public method vector<string> construct(string H, string V) · 96 test cases · 2 s / 256 MB per case

Submitting as anonymous