Connection Status:
Competition Arena > TrivialWordSearch

TrivialWordSearch

SRM 782 · 2020-03-26 · by misof

SRM 782 · 2020-03-26 · by misof · Greedy, Simple Search, Iteration, String Manipulation
Class Name: TrivialWordSearch
Return Type: String[]
Method Name: construct
Arg Types: (string)
Problem Statement

Problem Statement

Given is a String w that consists of uppercase English letters. Your task is to create a trivial word search puzzle: a square grid of letters that contains the given word w exactly once.

The word w can appear in any of the 8 cardinal directions (horizontally, vertically, or diagonally). An occurrence of a word is a set of positions in the grid that lie in one of those directions and contain the letters of w, in order. In particular, if w is a palindrome (i.e., reads the same forwards and backwards), it can still have only one occurrence in the grid, even though that occurrence can be read in two different directions.

Return any String[] with the following properties:

  • It describes a square grid of uppercase English letters.
  • Each letter in the grid appears somewhere in w.
  • The side of the grid must be at most 20.
  • The grid must contain exactly one occurrence of w.

If no such grid exists, return an empty String[] instead.

Constraints

  • w will contain between 1 and 10 characters, inclusive.
  • Each character in w will be an uppercase English letter ('A'-'Z').
Examples
0)
"DOG"
Returns: {"DGOODDO", "DODGOGG", "DGOODDD", "GOOGDGO", "GOGGOGD", "DOOGDOO", "OOGGOOD" }

The returned grid: DGOODDO DODGOGG DGOODDD GOOGDGO GOGGOGD DOOGDOO OOGGOOD The only occurrence of DOG in this grid: ******* ******* D****** *O***** **G**** ******* *******

1)
"ABBA"
Returns: {"BABA", "AABB", "ABAA", "ABAB" }

The only occurrence of ABBA is on the diagonal from the top right to the bottom left (or vice versa, as ABBA is a palindrome).

2)
"TOPCODER"
Returns: {"TOPTOPTOPTOP", "TOPTORTOPTOP", "TOPTOETOPTOP", "TOPTODTOPTOP", "TOPTOOTOPTOP", "TOPTOCTOPTOP", "TOPTOPTOPTOP", "TOPTOOTOPTOP", "TOPTOTTOPTOP", "TOPTOPTOPTOP", "TOPTOPTOPOOP", "TOPTOPTOPTOP" }
3)
"XXXXX"
Returns: { }

There is no valid word search grid that would contain exactly one occurrence of XXXXX. As the grid must be a square and you can only use the letter X, there will be many different occurrences of XXXXX in that grid.

4)
"E"
Returns: {"E" }

A word search puzzle doesn't get any more trivial than this.

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

Coding Area

Language: C++17 · define a public class TrivialWordSearch with a public method vector<string> construct(string w) · 103 test cases · 2 s / 256 MB per case

Submitting as anonymous