HuffmanDecoding
SRM 308 · 2006-06-24 · by Andrew_Lazarev
Problem Statement
When text is encoded using Huffman codes, each symbol is replaced by a string of 0s and 1s called a bit string representation. The replacement is done in such a way that the bit string representation of a symbol is never the prefix of the bit string representation of any other symbol. This property allows us to unambiguously decode the encoded text.
You will be given a
Constraints
- archive will contain between 1 and 50 characters, inclusive.
- archive will contain only the characters '0' (zero) and '1' (one).
- dictionary will contain between 1 and 26 elements, inclusive.
- Each element of dictionary will contain between 1 and 50 characters, inclusive.
- Each element of dictionary will contain only the characters '0' (zero) and '1' (one).
- No element of dictionary will be a prefix of any other element of dictionary.
- archive will be decodable using dictionary
"101101"
{"00","10","01","11"}
Returns: "BDC"
Because there are no elements in dictionary that are prefixes of other elements, only one element of dictionary will be a prefix of archive. In this case, it is the second element ("10") which represents 'B'. The rest of the text can be decoded using the same logic.
"10111010"
{"0","111","10"}
Returns: "CBAC"
Note that elements of dictionary can be of different lengths.
"0001001100100111001"
{"1","0"}
Returns: "BBBABBAABBABBAAABBA"
'1' is replaced by 'A', '0' is replaced by 'B'.
"111011011000100110"
{"010","00","0110","0111","11","100","101"}
Returns: "EGGFAC"
"001101100101100110111101011001011001010"
{"110","011","10","0011","00011","111","00010","0010","010","0000"}
Returns: "DBHABBACAIAIC"
Submissions are judged against all 55 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HuffmanDecoding with a public method string decode(string archive, vector<string> dictionary) · 55 test cases · 2 s / 256 MB per case