GPS Encoding
InterviewTime limit1sMemory limit128 MB
Given a letter permutation encoding numbers 0-25, find the shortest way to encode a digit string as letters using single digits or valid two-digit pairs, breaking ties by lexicographically largest result.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Greedy, String
- Solved
- No attempts yet
Problem
Traditionally, simple codes take a permutation of the alphabet, number each character from 01 to 26 (or 00 to 25), and encrypt a message as a string of digits. It is then easy to hide the structure of the text by breaking the string into fixed-length groups.
This problem turns that idea around: you are given a sequence of digits that you want to encrypt (perhaps a GPS location you want to send to a friend to tell her where a treasure is hidden). You could do it the simple way and use only 10 letters to encode the 10 digits, or you could use all 26 letters and spend the extra letters to encode suitable pairs of digits. For example, the sequence 941177 could be encoded as 9 4 1 1 7 7, as 9 4 11 7 7, or as 9 4 1 17 7.
You are given a permutation of the uppercase letters. It implicitly defines an encoding of the numbers 0, 1, …, 25: the letter in position i (counting from 0) encodes the number i. A number from 0 to 9 can stand for a single digit, and a number from 0 to 25 can stand for two consecutive digits (a pair whose value is at most 25, with a leading zero allowed). Given the permutation and a sequence of digits, find the shortest encryption of the sequence as a string of letters. Note that decrypting such a string may not be unique.
Input
The input consists of several encryption problems. Each problem begins with a line containing a permutation of the uppercase letters, followed by one or more lines, each containing a string of between 3 and 20 digits. The list of digit strings for a problem is terminated by a line containing a single 0. The whole input is terminated by a line containing a single #. These two terminator lines must not be processed.
Output
For each problem, print a line consisting of Problem followed by the problem number (a counter starting at 1). Then, for each digit string of that problem, print its shortest encoding on its own line. If several encodings share this shortest length, print the lexicographically greatest one (the one that would come last in a dictionary). Print a blank line between successive problems.