Statistics

Problem Statement for "TrivialWordSearch"

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.

Definition

Class:
TrivialWordSearch
Method:
construct
Parameters:
String
Returns:
String[]
Method signature:
String[] construct(String w)
(be sure your method is public)

Constraints

  • w will contain between 1 and 10 characters, inclusive.
  • Each character in w will be an uppercase English letter ('A'-'Z').

Examples

  1. "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**** ******* *******

  2. "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).

  3. "TOPCODER"

    Returns: {"TOPTOPTOPTOP", "TOPTORTOPTOP", "TOPTOETOPTOP", "TOPTODTOPTOP", "TOPTOOTOPTOP", "TOPTOCTOPTOP", "TOPTOPTOPTOP", "TOPTOOTOPTOP", "TOPTOTTOPTOP", "TOPTOPTOPTOP", "TOPTOPTOPOOP", "TOPTOPTOPTOP" }

  4. "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.

  5. "E"

    Returns: {"E" }

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

  6. "BB"

    Returns: { }

  7. "EY"

    Returns: { }

  8. "EEL"

    Returns: {"EEL", "LLL", "LLL" }

  9. "LEE"

    Returns: {"LEE", "LLL", "LLL" }

  10. "LOL"

    Returns: {"LOL", "LLL", "LLL" }

  11. "ACE"

    Returns: {"ACE", "AAA", "AAA" }

  12. "AAA"

    Returns: { }

  13. "EERR"

    Returns: {"EERR", "EEEE", "EEEE", "EEEE" }

  14. "HAHA"

    Returns: {"HAHA", "HHHH", "HHHH", "HHHH" }

  15. "POOP"

    Returns: {"POOP", "PPPP", "PPPP", "PPPP" }

  16. "EELE"

    Returns: {"EELE", "EEEE", "EEEE", "EEEE" }

  17. "LOOO"

    Returns: {"LOOO", "LLLL", "LLLL", "LLLL" }

  18. "UUUP"

    Returns: {"UUUP", "PPPP", "PPPP", "PPPP" }

  19. "TTTT"

    Returns: { }

  20. "ZZAA"

    Returns: {"ZZAA", "ZZZZ", "ZZZZ", "ZZZZ" }

  21. "TTUUUUUUUU"

    Returns: {"TTUUUUUUUU", "TTTTTTTTTT", "TTTTTTTTTT", "TTTTTTTTTT", "TTTTTTTTTT", "TTTTTTTTTT", "TTTTTTTTTT", "TTTTTTTTTT", "TTTTTTTTTT", "TTTTTTTTTT" }

  22. "TUUUUUUUU"

    Returns: {"TUUUUUUUU", "TTTTTTTTT", "TTTTTTTTT", "TTTTTTTTT", "TTTTTTTTT", "TTTTTTTTT", "TTTTTTTTT", "TTTTTTTTT", "TTTTTTTTT" }

  23. "GGGGGGGF"

    Returns: {"GGGGGGGF", "FFFFFFFF", "FFFFFFFF", "FFFFFFFF", "FFFFFFFF", "FFFFFFFF", "FFFFFFFF", "FFFFFFFF" }

  24. "GFGFFGFGF"

    Returns: {"GFGFFGFGF", "GGGGGGGGG", "GGGGGGGGG", "GGGGGGGGG", "GGGGGGGGG", "GGGGGGGGG", "GGGGGGGGG", "GGGGGGGGG", "GGGGGGGGG" }

  25. "FHDSFFSD"

    Returns: {"FHDSFFSD", "FFFFFFFF", "FFFFFFFF", "FFFFFFFF", "FFFFFFFF", "FFFFFFFF", "FFFFFFFF", "FFFFFFFF" }

  26. "DGDSSRRV"

    Returns: {"DGDSSRRV", "DDDDDDDD", "DDDDDDDD", "DDDDDDDD", "DDDDDDDD", "DDDDDDDD", "DDDDDDDD", "DDDDDDDD" }

  27. "QWERTYUIOP"

    Returns: {"QWERTYUIOP", "QQQQQQQQQQ", "QQQQQQQQQQ", "QQQQQQQQQQ", "QQQQQQQQQQ", "QQQQQQQQQQ", "QQQQQQQQQQ", "QQQQQQQQQQ", "QQQQQQQQQQ", "QQQQQQQQQQ" }

  28. "POPOPOPOPO"

    Returns: {"POPOPOPOPO", "PPPPPPPPPP", "PPPPPPPPPP", "PPPPPPPPPP", "PPPPPPPPPP", "PPPPPPPPPP", "PPPPPPPPPP", "PPPPPPPPPP", "PPPPPPPPPP", "PPPPPPPPPP" }

  29. "FFFFFFFFFF"

    Returns: { }

  30. "FLF"

    Returns: {"FLF", "FFF", "FFF" }

  31. "OCC"

    Returns: {"OCC", "OOO", "OOO" }

  32. "CCCZ"

    Returns: {"CCCZ", "ZZZZ", "ZZZZ", "ZZZZ" }

  33. "SSO"

    Returns: {"SSO", "OOO", "OOO" }

  34. "JJJ"

    Returns: { }

  35. "YWY"

    Returns: {"YWY", "YYY", "YYY" }

  36. "RNN"

    Returns: {"RNN", "RRR", "RRR" }

  37. "VVM"

    Returns: {"VVM", "MMM", "MMM" }

  38. "EDE"

    Returns: {"EDE", "EEE", "EEE" }

  39. "QLQ"

    Returns: {"QLQ", "QQQ", "QQQ" }

  40. "BBB"

    Returns: { }

  41. "FFJ"

    Returns: {"FFJ", "JJJ", "JJJ" }

  42. "HQQH"

    Returns: {"HQQH", "HHHH", "HHHH", "HHHH" }

  43. "TTT"

    Returns: { }

  44. "IIU"

    Returns: {"IIU", "UUU", "UUU" }

  45. "JJJU"

    Returns: {"JJJU", "UUUU", "UUUU", "UUUU" }

  46. "ZKZ"

    Returns: {"ZKZ", "ZZZ", "ZZZ" }

  47. "QII"

    Returns: {"QII", "QQQ", "QQQ" }

  48. "AHH"

    Returns: {"AHH", "AAA", "AAA" }

  49. "MMM"

    Returns: { }

  50. "UEEU"

    Returns: {"UEEU", "UUUU", "UUUU", "UUUU" }

  51. "PPP"

    Returns: { }

  52. "LQQ"

    Returns: {"LQQ", "LLL", "LLL" }

  53. "EAE"

    Returns: {"EAE", "EEE", "EEE" }

  54. "IXI"

    Returns: {"IXI", "III", "III" }

  55. "YRY"

    Returns: {"YRY", "YYY", "YYY" }

  56. "JJJ"

    Returns: { }

  57. "AJJ"

    Returns: {"AJJ", "AAA", "AAA" }

  58. "LII"

    Returns: {"LII", "LLL", "LLL" }

  59. "KFK"

    Returns: {"KFK", "KKK", "KKK" }

  60. "EYY"

    Returns: {"EYY", "EEE", "EEE" }

  61. "MMM"

    Returns: { }

  62. "VVVK"

    Returns: {"VVVK", "KKKK", "KKKK", "KKKK" }

  63. "CXC"

    Returns: {"CXC", "CCC", "CCC" }

  64. "HOHH"

    Returns: {"HOHH", "HHHH", "HHHH", "HHHH" }

  65. "PYY"

    Returns: {"PYY", "PPP", "PPP" }

  66. "YYY"

    Returns: { }

  67. "OOOO"

    Returns: { }

  68. "AAA"

    Returns: { }

  69. "ZZZZ"

    Returns: { }

  70. "ZZZ"

    Returns: { }

  71. "JOO"

    Returns: {"JOO", "JJJ", "JJJ" }

  72. "IXX"

    Returns: {"IXX", "III", "III" }

  73. "WWW"

    Returns: { }

  74. "VVU"

    Returns: {"VVU", "UUU", "UUU" }

  75. "HKH"

    Returns: {"HKH", "HHH", "HHH" }

  76. "AUA"

    Returns: {"AUA", "AAA", "AAA" }

  77. "EMEM"

    Returns: {"EMEM", "EEEE", "EEEE", "EEEE" }

  78. "OOO"

    Returns: { }

  79. "LLL"

    Returns: { }

  80. "AB"

    Returns: { }

  81. "TO"

    Returns: { }

  82. "DO"

    Returns: { }

  83. "DDG"

    Returns: {"DDG", "GGG", "GGG" }

  84. "TTO"

    Returns: {"TTO", "OOO", "OOO" }

  85. "A"

    Returns: {"A" }

  86. "BE"

    Returns: { }

  87. "AAAAAAB"

    Returns: {"AAAAAAB", "BBBBBBB", "BBBBBBB", "BBBBBBB", "BBBBBBB", "BBBBBBB", "BBBBBBB" }

  88. "DDAAA"

    Returns: {"DDAAA", "DDDDD", "DDDDD", "DDDDD", "DDDDD" }

  89. "AAAAB"

    Returns: {"AAAAB", "BBBBB", "BBBBB", "BBBBB", "BBBBB" }

  90. "AAB"

    Returns: {"AAB", "BBB", "BBB" }

  91. "TA"

    Returns: { }

  92. "XXXE"

    Returns: {"XXXE", "EEEE", "EEEE", "EEEE" }

  93. "XSS"

    Returns: {"XSS", "XXX", "XXX" }

  94. "XA"

    Returns: { }

  95. "ABC"

    Returns: {"ABC", "AAA", "AAA" }

  96. "AAAC"

    Returns: {"AAAC", "CCCC", "CCCC", "CCCC" }

  97. "AAAB"

    Returns: {"AAAB", "BBBB", "BBBB", "BBBB" }

  98. "DA"

    Returns: { }

  99. "CAAA"

    Returns: {"CAAA", "CCCC", "CCCC", "CCCC" }

  100. "AW"

    Returns: { }

  101. "BA"

    Returns: { }

  102. "ABBBB"

    Returns: {"ABBBB", "AAAAA", "AAAAA", "AAAAA", "AAAAA" }

  103. "ABB"

    Returns: {"ABB", "AAA", "AAA" }

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.
This problem was used for: