No Pause Telegraph
InterviewTime limit1sMemory limit128 MB
Given a string of dots and dashes and seven fixed letter codes, split it into codewords that minimize the resulting message alphabetically, or report that no split exists.
- Level
Medium5 of 10
- Topics
- Dynamic programming, String, Greedy, Trie
- Solved
- No attempts yet
Problem
Long ago, a country was at war. To keep in touch with its allied cities, the country used telegraph machines to send Morse code messages. In Morse code each letter is written using only . (dot) and - (dash), and a short pause is placed between letters so they can be told apart.
Because telegraph messages could be intercepted, a machine that encoded the messages was built, called the No Pause Telegraph. It works just like an ordinary telegraph, except that it sends the codes back to back with no pause between letters.
An archaeologist studying old relics succeeded in analyzing the code and identified the 7 letters used on the relics:
Your task is to decode messages written by this machine. Because there are no pauses, a single code string can sometimes be read in more than one way. For example, if some letter X had the code . and another letter Y had the code .., then two dots in a row could mean either XX or Y. Whenever several readings are possible, output only the alphabetically smallest message.
Input
Each line of input is one message encoded by the No Pause Telegraph. Every line consists only of the characters . (dot) and - (dash). Process each line until the end of input.
Output
For each input line, print on its own line the alphabetically smallest message that the line can represent. If the line cannot be decoded into any message, print could not be translated (without the quotes).