Dictionary encoding replaces repeated values with compact integer codes. Columnar databases use it to reduce storage and make comparisons operate on small integers instead of repeated strings.
Design a DictionaryEncoder class:
DictionaryEncoder() creates an empty dictionary.int encode(String value) returns the stable code for value. The first distinct value receives code 0, and each later distinct value receives the next consecutive integer. Repeated values reuse their existing code.String decode(int code) returns the value assigned to code.
Every decode call uses a valid code previously returned by the same object. Separate encoder objects have independent dictionaries and each starts at code 0.
Example 1:
Input:
Output:
Explanation: Apple receives code 0 and banana receives code 1. Encoding apple again reuses 0, and decoding 1 returns banana.
Example 2:
Input:
Output:
Explanation: Codes follow first-seen order and decode directly to the original values.
Constraints
- At most
10^5 method calls are made. - Values contain at most
100 characters. - Each
decode receives 0 <= code < distinctValues. - Values are compared exactly and may be empty.
Design a Dictionary Encodermedium