FastPrep
Problem · Trie

The Huffman Decoder 🌼

Learn this problem
● EasyWolverine TradingFULLTIMEOA

Problem statement

Huffman codes compress text by assigning the characters that occur at the highest frequency the shortest possible codes. In this encoding scheme, no code can be a prefix of another. For example, if the code for a is 01, then the code for b cannot be 011.

Given an array of Huffman code mappings and a Huffman-encoded string, find the decoded string. Each mapping will be a string consisting of a tab-separated ('\t') character and its encoded value: 'c encoded value' where the whitespace is a tab character. The newline character is represented as the character [newline] in the codes list, but should translate to \n when decoded.

Note: While all code mappings in the example are 6 digits long, mappings can be different lengths. The algorithm creates the shortest length mapping for the most frequent character encoded.

Function

decode(codes: String[], encoded: String) → String

Complete the function decode in the editor below. The function must return the decoded string.

decode has the following parameter(s):

  • string codes[n]: an array of character mappings in the form "character\tmapping"
  • encoded: an encoded string

    • Examples

    Example 1

    codes = ["a\t100100", "b\t100101", "[newline]\t111111"]encoded = "100100111111100101"return = "a\nb"
    The output is "a\nb". There is a newline inbetween a and b.

    Constraints

  • 1 ≤ n ≤ 100
  • 1 ≤ |encoded| ≤ 7000
  • All characters of encoded are either '0' or '1'
  • All inputs will represent a valid Huffman encoded string
  • An encoded character may be a letter, space, [newline], or punctuation, e.g. dot, comma, etc.

    • More Wolverine Trading problems

    drafts saved locally
    public String decode(String[] codes, String encoded) {
    // write your code here
}
    codes["a\t100100", "b\t100101", "[newline]\t111111"]
    encoded"100100111111100101"
    expected"a\nb"
    checking account