Statistics

Problem Statement for "HuffmanDecoding"

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 String archive and a String[] dictionary. The i-th element of dictionary will be the bit string representation of the i-th uppercase letter. Decode archive using dictionary and return the result as a single String.

Definition

Class:
HuffmanDecoding
Method:
decode
Parameters:
String, String[]
Returns:
String
Method signature:
String decode(String archive, String[] dictionary)
(be sure your method is public)

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

Examples

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

  2. "10111010"

    {"0","111","10"}

    Returns: "CBAC"

    Note that elements of dictionary can be of different lengths.

  3. "0001001100100111001"

    {"1","0"}

    Returns: "BBBABBAABBABBAAABBA"

    '1' is replaced by 'A', '0' is replaced by 'B'.

  4. "111011011000100110"

    {"010","00","0110","0111","11","100","101"}

    Returns: "EGGFAC"

  5. "001101100101100110111101011001011001010"

    {"110","011","10","0011","00011","111","00010","0010","010","0000"}

    Returns: "DBHABBACAIAIC"

  6. "00000000000000000000000000000000000000000000000000"

    {"00000000000000000000000000000000000000000000000000", "11111111111111111111111111111111111111111111111111"}

    Returns: "A"

  7. "00000000000000000000000000000000000000000000000000"

    {"0", "11111111111111111111111111111111111111111111111111"}

    Returns: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

  8. "00000000000000000000000000000000000000000000000000"

    {"0"}

    Returns: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

  9. "11111111111111111111111111111111111111111111111111"

    {"1"}

    Returns: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

  10. "10101010101010101010101010101010101010101010101010"

    {"1","0"}

    Returns: "ABABABABABABABABABABABABABABABABABABABABABABABABAB"

  11. "0011101011111011001011001111001000111101011111111"

    {"010","1110","1101","000","0111","1111","0110","001","1100","10"}

    Returns: "HCECJAIFHDFAFF"

  12. "010011010010001010001001000100100100110110101000"

    {"1","000","010","011","001"}

    Returns: "CDCCECEEBAEEEADCAB"

  13. "0110000011111100010110011110110011110111011101101"

    {"100","111","110","01","00","101"}

    Returns: "DAEDBCEFABFABFCBDF"

  14. "0100110000111000010000000100000101010101000001001"

    {"0001","0101","11","011","10","0000","0100","001"}

    Returns: "GCFCEAFAFBBGAH"

  15. "1110101100010011001100000111110011010110110001010"

    {"1101","00","011","1100","10","111","010"}

    Returns: "FGDGCBDBCFBACCBGE"

  16. "100010011110000100111110010101000110100"

    {"101","100","11","0"}

    Returns: "BDBCCDDDDBCCBADBDCDB"

  17. "000110001110110100110001101001001110110100101110"

    {"0111","01100","10","1110","010","110","011010","1111","00","011011"}

    Returns: "IBAGBGEAGED"

  18. "101001110100000110001111111011111100110011001000"

    {"1010","1110","01","000","1000","110","1011","1111","1001","001"}

    Returns: "ACFEJEHBHFCIID"

  19. "1001101001110001000101101010001011000100111001000"

    {"1001","11","1000","011","10110","00","1010","010","10111"}

    Returns: "AGDCCEGFEFABFC"

  20. "0110011101100111011001100110011001100110010011111"

    {"0111","1","00","0110","010"}

    Returns: "DADADDDDDDEABB"

  21. "00001010100101001011"

    {"0","1"}

    Returns: "AAAABABABAABABAABABB"

  22. "0001001011001000000110011010100011010100100001001"

    {"110","0000","100","0110","0001","101","0111","001","010","111"}

    Returns: "EHDIBDDFEFIIEH"

  23. "1010110101110010111010110001111110001010110110"

    {"00","111","01","110","10"}

    Returns: "EEDEBAEBCCEABBACCCED"

  24. "0011010011100000001000010010010111110010011011100"

    {"101","0000","1101","100","0001","111","01","001","1100"}

    Returns: "HAHIBGBDDAFDDCI"

  25. "110110011101110011101100001011110110011110001010"

    {"110","011","00","111","01010","01011","0100","100","101"}

    Returns: "AABIABIHCIDBCDHE"

  26. "110011100111011101110011100101100110011011111000"

    {"0","11000","1101","111","101","100","11001"}

    Returns: "GGCCGGAGFCDFA"

  27. "111111101011010101011110101101001011"

    {"0","11","10"}

    Returns: "BBBCCBACCCBBACBACACB"

  28. "000010001111000000110001000110101"

    {"1","00","01"}

    Returns: "BBABCAAABBBAABCBCACC"

  29. "1110010110111101011000111101011110111101010111100"

    {"00","010","1100","1110","011","1111","10","11011","11010"}

    Returns: "DBHICEIFEIGFA"

  30. "0011001100110100001100100110101000001000110010011"

    {"0101","011","0000","0100","0001","1","0010","0011"}

    Returns: "HHHDHGBACDBGB"

  31. "0011101111010010110011010100110000011010110101100"

    {"11010110101","111","110100","110000100","0000","100","1100011","110011","1101011011","1100000","1100010","11010111","11010100","110101011","001","110101010","11011","110101100","0001","01","101","110010","11010110100","11000011","110000101"}

    Returns: "OQCUFMJAF"

  32. "0011101100010110111100100100101011011100101100110"

    {"01011","001001","0010100","00110","001000","111","001010100","00101100","00111","01010","0010111","10","00101101","0110","01001","00101011","000","001010101","110","0111","01000"}

    Returns: "INMFBPTHS"

  33. "101101001010001000111011100101011100010111000010"

    {"101110011","010","11","100110","100001","10110","001","011","101110010","1000000","10111000","000","101111","1000101","10010","100011","100111","1000100","10111011","1000001","10111010","1010"}

    Returns: "FORHIKKB"

  34. "0101111101010111001010001000110100100001010101111"

    {"0011001","0110","11","0010","0011000","01010","01011001","0111","001101","01000","001110","01011000","100","0101101","0101111","000","101","001111","0101110","01001"}

    Returns: "OQSFDIDPQO"

  35. "110010100110010110010011110111000101010010101001"

    {"101000","101001","1100","1000","1111","0011","0001","0000101","1110","010","0010","1101","10010","101010","01100","100111","100110","00000","1011","01101","0000100","000011","0111","101011"}

    Returns: "CBMCPSDNJB"

  36. "1101000011100001100100011001111011101110111011011"

    {"001","10101","110101","10100","10110","01","1000","000","10111101","1101000","10011","10111100","110001","1100101","1111","10010","101110","110000","10111110","1101001","11011","1100100","1110","110011","10111111"}

    Returns: "JFRVFKUQWU"

  37. "1111001000011100001011000101000010111111010011011"

    {"1000011","1011","111010","100010","1110110","100000","00","10000101","111100","111111","1010","111110","111101","1110111","111001","111000","110","01","1001","10000100","100011"}

    Returns: "IAHDHLSB"

  38. "1010100111101111011000110110101101100011011111100"

    {"101101","11101","10001100","10111","1000110110","10001110","111101","111100","10011011","10011010","11111","100011010","101100","1001111","10001111","1000110111","10010","1010","10000","1001110","0","110","1001100","100010","11100"}

    Returns: "RNUGEAPY"

  39. "111111111101011111111110001100110110110001000111"

    {"0111","1011","1110","0100","11010","1001","00","111100","1111010","0101","011010","110111","1100","1000","111110","01100","011011","1010","1111011","111111","110110"}

    Returns: "TITHPUMDA"

  40. "0100010101110001010100000101010000111000101010101"

    {"0010101111","00100","00000","0111","0011","0110","0001","00001110","000010","0010101110","001011","001010110","000011111","100","0010100","0000110","010","00101010","11","101","000011110"}

    Returns: "QJRITHRT"

  41. "10111101100110001100111011011100011100001101001"

    {"1101111","011","111010","1011","0011","1101001","1111","000","110001","110010","1101100","1001","11100","1101000","0010","10001","1010","110011","10000","1101101","010","111011","110000","1101110","110101"}

    Returns: "DKILTIWF"

  42. "0000100000100100000100110000010010000101000110111"

    {"0001001000","0001001001","0000011","0100","0101","00011","0000010","000000","0011","0001001100","000100111","0001001101","1101","1100","000010","0001000","0001001011","0001001010","0000111","0111","111","0000110","10","000101","0010","0110"}

    Returns: "OODJAEFT"

  43. "001110000011000011100100111000001010111010001001"

    {"110","11101","11110","00010","00111000","00100","001111","00011","00111001","001100","0011101","00001","001010","11111","00000","001101","01","10","001011","11100"}

    Returns: "EJIEMBDQ"

  44. "0000001110011111110010000110010000101001110101101"

    {"000000110","101","100","0010110","001010","0111","000001","0001","0110","00100","0101","0000000","0100","00110","00000010","000011","0010111","000000111","000010","00111","11"}

    Returns: "RTUUJNMEFKB"

  45. "1011010001111100101101110001011001011000110001100"

    {"1110","0","110100","110101","110010","1111","100000","1000111","110001","1000010","1000110","100010","10110","110011","11011","1000011","1001","1010","110000","10111"}

    Returns: "MHEOLEIKB"

  46. "1011100100011101101110100011111011101101100010101"

    {"1010001","101110000","101110001","1011000","000","10101","011","110","1011111","1011001","101001","111","1000","1011101","010","1011011","1011100101","1011010","1010000","1001","1011100100","1011110","101110011","001"}

    Returns: "UGPALNDF"

  47. "011100000110100000110101100101110000111101000111"

    {"0001001","0001000","1000010","1010","0000111","001","00001100","1000011","10011","000110","1011","000010","000101","000111","011","10001","010","1101","10010","000000","000001","1100","00001101","100000","111"}

    Returns: "OXRUDVKHRN"

  48. "1001101100001010101000011111101110100000100001000"

    {"110","1000111","100000","10111","100111","10000110","101101","1011001","1000101","1001101","10010","1111","1110","1000110","1011000","1000100","0","1010","1000010","10000111","1001100"}

    Returns: "JSRTMMCSQQ"

  49. "110001110011110100011111110110011000110011001100"

    {"1111011","00011","0010","0100","1111000","0000","011000","001110","0011111","1111001","0011110","101","110","11100","1111010","01111","0101","01101","011001","01110","111010","11111","00010","100","00110","111011"}

    Returns: "MHPDPZYYSX"

  50. "01001111010010010011001000001010001101001000010"

    {"01101","01110","01001110","0100110","00010","01000","0101","0000","001001","111","010011111","1010","100","0100111101","00101","01100","00011","010010","1011","0011","1101","0100111100","01111","001000","1100"}

    Returns: "NITXOQRE"

  51. "11111111111111111111111111111111111111111111111111"

    {"0", "1"}

    Returns: "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

  52. "0001001100100111001"

    {"1", "0" }

    Returns: "BBBABBAABBABBAAABBA"

  53. "0000100111001001111001"

    {"1", "0" }

    Returns: "BBBBABBAAABBABBAAAABBA"

  54. "001101100101100110111101011001011001010"

    {"110", "011", "10", "0011", "00011", "111", "00010", "0010", "010", "0000" }

    Returns: "DBHABBACAIAIC"

  55. "000100110010011"

    {"1", "0" }

    Returns: "BBBABBAABBABBAA"

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: