Statistics

Problem Statement for "MessageMess"

Problem Statement

It is a common practice in cryptography to remove the spaces from a message before encoding it to help to disguise its structure. Even after it is then decoded, we are left with the problem of putting the spaces back in the message.

Create a class MessageMess that contains a method restore that takes a String[] dictionary of possible words and a String message as inputs. It returns the message with single spaces inserted to divide the message into words from the dictionary. If there is more than one way to insert spaces, it returns "AMBIGUOUS!" If there is no way to insert spaces, it returns "IMPOSSIBLE!" The return should never have any leading or trailing spaces.

Definition

Class:
MessageMess
Method:
restore
Parameters:
String[], String
Returns:
String
Method signature:
String restore(String[] dictionary, String message)
(be sure your method is public)

Notes

  • Don't forget the '!' at the end of the two special returns
  • A proper message may require 0 spaces to be inserted

Constraints

  • dictionary will contain between 1 and 50 elements inclusive
  • the elements of dictionary will be distinct
  • each element of dictionary will contain between 1 and 50 characters
  • message will contain between 1 and 50 characters
  • every character in message and in each element of dictionary will be an uppercase letter 'A'-'Z'

Examples

  1. {"HI", "YOU", "SAY"}

    "HIYOUSAYHI"

    Returns: "HI YOU SAY HI"

    A word from dictionary may appear multiple times in the message.

  2. {"ABC", "BCD", "CD", "ABCB"}

    "ABCBCD"

    Returns: "AMBIGUOUS!"

    "ABC BCD" and "ABCB CD" are both possible interpretations of message.

  3. {"IMPOSS", "SIBLE", "S"}

    "IMPOSSIBLE"

    Returns: "IMPOSSIBLE!"

    There is no way to concatenate words from this dictionary to form "IMPOSSIBLE"

  4. {"A","B","C","D"}

    "BADCAB"

    Returns: "B A D C A B"

  5. {"A","B","C","D"}

    "ABRACADABRA"

    Returns: "IMPOSSIBLE!"

  6. {"APPLE","APPLET","ET"}

    "APPLET"

    Returns: "APPLET"

  7. {"A","BA","BAB","AR"}

    "ABABABABABABABABABABABABABABABABABABABABABABABAR"

    Returns: "AMBIGUOUS!"

  8. {"A","BA","BABA","AR","ABA"}

    "ABABABABABABABABABABABABABABABABABABABABABABABAR"

    Returns: "IMPOSSIBLE!"

  9. {"A","BA","BABA","AR","ABA","ABAB"}

    "ABABABABABABABABABABABABABABABABABABABABABABAR"

    Returns: "ABAB ABAB ABAB ABAB ABAB ABAB ABAB ABAB ABAB ABAB ABAB AR"

  10. {"TA","PEA","DOG","CAT","APE","TAPE"}

    "TAPEAPEAPE"

    Returns: "TAPE APE APE"

  11. {"AB","BA","AA","BB","BABAAB","ABAAAB","BAAB","BABA","BBBA","BAAA"}

    "ABBAABBBABABBAABAAABAAAABABAAABABABAAABABABABAABA"

    Returns: "IMPOSSIBLE!"

  12. {"AB","BA","AA","BB","BABAAB"}

    "ABBAABBBABABBAABAAABAAAABABAAABABABAAABABABABAABAA"

    Returns: "AMBIGUOUS!"

  13. {"A","B","C","BAB","BAD","E","F","G","H","I","J","K","L","EF","M","N", "O","P","Q","R","S","T","U","V","W","X","Y","Z"}

    "BAABAABBAAABAABAABAABBBBADEEABAAAABAAABAABBBBAFBAA"

    Returns: "B A A B A A B B A A A B A A B A A B A A B B B BAD E E A B A A A A B A A A B A A B B B B A F B A A"

  14. {"XYX"}

    "XYXXYXXYXXYXXYXXYX"

    Returns: "XYX XYX XYX XYX XYX XYX"

  15. {"IMPOSS", "SIBLE", "S", "IMPOSSIBLE"}

    "IMPOSSIBLE"

    Returns: "IMPOSSIBLE"

    This message can be decoded without ambiguity. This requires the insertion of no spaces since the entire message appears as a word in the dictionary.

  16. {"AB","AC","A"}

    "A"

    Returns: "A"

  17. {"AB","AC","A"}

    "C"

    Returns: "IMPOSSIBLE!"

  18. { "A", "B", "AB", "BA", "ABA", "BAB", "ABAB", "BABA", "ABABA", "BABAB", "ABABAB", "BABABA", "ABABABA", "BABABAB", "ABABABABABABABABABABABAC" }

    "ABABABABABABABABABABABACABABABABABABABABABABABAC"

    Returns: "ABABABABABABABABABABABAC ABABABABABABABABABABABAC"

  19. { "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAAA", "AAAAAAA", "AAAAAAAA", "AAAAAAAAA", "AAAAAAAAAA", "AAAAAAAAAAA", "AAAAAAAAAAAA", "AAAAAAAAAAAAA", "AAAAAAAAAAAAAA", "AAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "AMBIGUOUS!"

  20. { "A", "B", "AA", "AB", "BA", "BB", "AAA", "AAB", "ABA", "BAA", "BBB", "BBA", "BAB", "ABB", "AAAA", "AAAB", "AABA", "ABAA", "BAAA", "BBBB", "BBBA", "BBAB", "BABB" }

    "ABABBBABABBBABABBAAABABBAAABBABABBBABABBBABABBC"

    Returns: "IMPOSSIBLE!"

  21. { "IMPOSS", "SIBLE", "S" }

    "IMPOSSIBLE"

    Returns: "IMPOSSIBLE!"

  22. { "AA", "AAAA", "AAAAAA", "AAAAAAAA", "AAAAAAAAAA", "AAAAAAAAAAAA", "AAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "IMPOSSIBLE!"

  23. { "BLAH", "BLA" }

    "BLAHA"

    Returns: "IMPOSSIBLE!"

  24. { "AB", "CD", "ABCD" }

    "ABCD"

    Returns: "AMBIGUOUS!"

  25. { "A", "AA", "AAA", "AAAA", "AAAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAC"

    Returns: "IMPOSSIBLE!"

  26. { "A", "AA", "AAA", "AAAA", "AAAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "AMBIGUOUS!"

  27. { "A", "AA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"

    Returns: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"

  28. { "H", "HH", "HHCH" }

    "HHHHHHHHHHHHHHHHHHHHHHHHHHHCHHHHHHHHHHHHHHHHHHHHC"

    Returns: "IMPOSSIBLE!"

  29. { "A", "AB", "ABC", "ABCD", "ABCDE", "ABCDEF", "ABCDEFG", "BCDEFG", "CDEFG", "DEFG", "EFG", "FG", "G", "B", "C", "D", "E", "F", "BC", "CD", "DE", "EF", "BCD", "CDE", "DEF", "BCDE", "CDEF", "BCDEF" }

    "ABCDEFGABCDEFGABCDEFGABCDEFGZ"

    Returns: "IMPOSSIBLE!"

  30. { "AB", "CD", "EF", "ABC" }

    "ABCDEF"

    Returns: "AB CD EF"

  31. { "AB", "CDEF", "CD" }

    "ABCDEF"

    Returns: "AB CDEF"

  32. { "A", "AA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "AMBIGUOUS!"

  33. { "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAAA", "AAAAAAA", "AAAAAAAA", "AAAAAAAAA", "AAAAAAAAAA", "AAAAAAAAAAA", "AAAAAAAAAAAA", "AAAAAAAAAAAAA", "AAAAAAAAAAAAAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "AMBIGUOUS!"

  34. { "A", "AA", "AAA", "AAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAB"

    Returns: "IMPOSSIBLE!"

  35. { "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAAA", "AAAAAAA", "AAAAAAAA", "AAAAAAAAA", "AAAAAAAAAA", "AAAAAAAAAAA", "AAAAAAAAAAAA", "AAAAAAAAAAAAA", "AAAAAAAAAAAAAA", "AAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"

    Returns: "IMPOSSIBLE!"

  36. { "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAAA", "AAAAAAA", "AAAAAAAA", "AAAAAAAAA", "AAAAAAAAAA", "AAAAAAAAAAA", "AAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"

    Returns: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"

  37. { "ABC", "AB", "CD" }

    "ABCD"

    Returns: "AB CD"

  38. { "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAC"

    Returns: "IMPOSSIBLE!"

  39. { "ABC", "AB", "C" }

    "ABC"

    Returns: "AMBIGUOUS!"

  40. { "A", "B", "C", "D", "E", "F", "G", "AB", "BC", "CD", "DE", "EF", "FG", "ABC", "BCD", "CDE", "DEF", "EFG", "ABCD", "BCDE", "CDEF", "DEFG", "ABCDE", "BCDEF", "CDEFG", "ABCDEF", "BCDEFG", "ABCDEFG" }

    "ABCDEFGABCDEFGABCEDFGABCDEFGABCDEFGZ"

    Returns: "IMPOSSIBLE!"

  41. { "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAAA", "AAAAAAA", "AAAAAAAA", "AAAAAAAAA", "AAAAAAAAAA", "AAAAAAAAAAA", "AAAAAAAAAAAA", "AAAAAAAAAAAAA", "AAAAAAAAAAAAAA", "AAAAAAAAAAAAAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "AMBIGUOUS!"

  42. { "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAAA", "AAAAAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAC"

    Returns: "IMPOSSIBLE!"

  43. { "A", "AA", "AAA", "AAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAB"

    Returns: "IMPOSSIBLE!"

  44. { "A", "G", "B", "C", "D", "E", "F", "AB", "BC", "CD", "DE", "EF", "FG", "ABC", "BCD", "CDE", "DEF", "EFG", "ABCD", "BCDE", "CDEF", "DEFG" }

    "ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGZ"

    Returns: "IMPOSSIBLE!"

  45. { "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAC"

    Returns: "IMPOSSIBLE!"

  46. { "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAAA", "AAAAAAA", "AAAAAAAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"

    Returns: "IMPOSSIBLE!"

  47. { "AA", "BB", "A", "B", "AB", "BA", "BBB", "AAA", "ABAB" }

    "AABBABABABBBBABAAAABBBABABABAAABBB"

    Returns: "AMBIGUOUS!"

  48. { "A", "AA", "AAA", "AAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"

    Returns: "IMPOSSIBLE!"

  49. { "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAAA", "AAAAAAA", "AAAAAAAA", "AAAAAAAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "AMBIGUOUS!"

  50. { "AB", "C", "ABC" }

    "ABC"

    Returns: "AMBIGUOUS!"

  51. { "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAAA" }

    "AAAAAAAA"

    Returns: "AMBIGUOUS!"

  52. { "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAAA", "AAAAAAA", "AAAAAAAA", "AAAAAAAAA", "AAAAAAAAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "AMBIGUOUS!"

  53. { "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAAA", "AAAAAAA", "AAAAAAAAAA", "AAAAAAAAAAAAAAAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"

    Returns: "IMPOSSIBLE!"

  54. { "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAAA" }

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "AMBIGUOUS!"

  55. { "ABC", "BCD", "CD", "ABCB" }

    "ABCBCD"

    Returns: "AMBIGUOUS!"

  56. { "HI", "H", "I" }

    "HI"

    Returns: "AMBIGUOUS!"

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: