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 Description
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 stringExample 1:
Input: codes = ["a 100100", "b 100101", "[newline] 111111"], encoded = "100100111111100101"
Output: "a b"
Explanation:The output is "a\nb". There is a newline inbetween a and b.
- 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.
input:
output: