MessageMess

SRM 149 · 2003-06-02 · by dgoodman

SRM 149 · 2003-06-02 · by dgoodman · Dynamic Programming, Encryption/Compression

Show categories

Class Name: MessageMess

Return Type: String

Method Name: restore

Arg Types: (vector<string>, string)

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.

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

{"HI", "YOU", "SAY"}
"HIYOUSAYHI"
Returns: "HI YOU SAY HI"

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

{"ABC", "BCD", "CD", "ABCB"}
"ABCBCD"
Returns: "AMBIGUOUS!"

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

{"IMPOSS", "SIBLE", "S"}
"IMPOSSIBLE"
Returns: "IMPOSSIBLE!"

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

{"A","B","C","D"}
"BADCAB"
Returns: "B A D C A B"

{"A","B","C","D"}
"ABRACADABRA"
Returns: "IMPOSSIBLE!"

14)

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

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

Coding Area

Language: C++17 · define a public class MessageMess with a public method string restore(vector<string> dictionary, string message) · 56 test cases · 2 s / 256 MB per case