You are given a character array keys containing unique characters and a string array values containing strings of length 2. You are also given another string array dictionary that contains all permitted original strings after decryption. You should implement a data structure that can encrypt or decrypt a 0-indexed string.
A string is encrypted with the following process:
c in the string, we find the index i satisfying keys[i] == c in keys.c with values[i] in the string.Note that in case a character of the string is not present in keys, the encryption process cannot be carried out, and an empty string "" is returned.
A string is decrypted with the following process:
s of length 2 occurring at an even index in the string, we find an i such that values[i] == s. If there are multiple valid i, we choose any one of them. This means a string could have multiple possible strings it can decrypt to.s with keys[i] in the string.Implement the Encrypter class:
Encrypter(char[] keys, String[] values, String[] dictionary) Initializes the Encrypter class with keys, values, and dictionary.String encrypt(String word1) Encrypts word1 with the encryption process described above and returns the encrypted string.int decrypt(String word2) Returns the number of possible strings word2 could decrypt to that also appear in dictionary.
Example 1:
Input
["Encrypter", "encrypt", "decrypt"]
[[['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]], ["abcd"], ["eizfeiam"]]
Output
[null, "eizfeiam", 2]
Explanation
Encrypter encrypter = new Encrypter([['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]);
encrypter.encrypt("abcd"); // return "eizfeiam".
// 'a' maps to "ei", 'b' maps to "zf", 'c' maps to "ei", and 'd' maps to "am".
encrypter.decrypt("eizfeiam"); // return 2.
// "ei" can map to 'a' or 'c', "zf" maps to 'b', and "am" maps to 'd'.
// Thus, the possible strings after decryption are "abad", "cbad", "abcd", and "cbcd".
// 2 of those strings, "abad" and "abcd", appear in dictionary, so the answer is 2.
Constraints:
1 <= keys.length == values.length <= 26values[i].length == 21 <= dictionary.length <= 1001 <= dictionary[i].length <= 100keys[i] and dictionary[i] are unique.1 <= word1.length <= 20002 <= word2.length <= 200word1[i] appear in keys.word2.length is even.keys, values[i], dictionary[i], word1, and word2 only contain lowercase English letters.200 calls will be made to encrypt and decrypt in total.Problem Overview: Design a class that encrypts a word by mapping each character to a fixed two‑character string, and decrypts an encrypted string by counting how many words from a dictionary could produce it.
Approach 1: Direct Mapping Approach (Hash Map + Dictionary Scan) (Encrypt: O(n), Decrypt: O(D * L))
Store a char → string mapping in a hash table for fast encryption. Encryption is straightforward: iterate through the input string, look up each character in the map, and append the mapped value. For decryption, iterate through every word in the dictionary, encrypt it using the same mapping, and compare the result with the encrypted query string. This works because the dictionary size is limited, but it can be expensive when many dictionary words must be re‑encrypted for each query.
Approach 2: Preprocessed Decryption Using Trie (O(n) encrypt, O(branch^k) decrypt with pruning)
Instead of re‑encrypting the dictionary every time, preprocess it. Build a reverse mapping from encrypted value → possible characters, then insert all dictionary words into a Trie. During decryption, process the encrypted string in 2‑character chunks. For each chunk, use the reverse map to find all candidate characters, then traverse the Trie to check whether those characters can continue a valid dictionary word. The Trie prunes invalid paths early, so you only explore prefixes that actually exist in the dictionary.
This approach shifts work to preprocessing. Encryption still performs a simple lookup per character, but decryption becomes a guided search constrained by the dictionary structure. In practice it avoids recomputing encrypted forms and drastically reduces unnecessary comparisons.
Recommended for interviews: Start with the direct hash‑map mapping to show you understand the encryption rule and dictionary validation. Then move to the Trie‑based preprocessing solution. Interviewers expect candidates to recognize that naive dictionary scanning repeats work and that building a Trie allows efficient prefix pruning during decryption.
This approach uses direct mapping for both encryption and decryption. We maintain a dictionary for fast lookup. For encryption, we map each character to its corresponding encrypted string. For decryption, we have to handle potential multiple mappings by considering each possibility in sequence. This is done using a dictionary to quickly reference mappings.
The Encrypter class uses dictionaries: char_to_encrypted for quick encryption lookups and encrypted_to_chars to map encrypted sub-strings back to possible characters for decryption. Encryption builds a string by replacing each character with its encrypted version. Decryption uses backtracking to test all possible decryptions against the dictionary.
Time Complexity: Encryption is O(n), where n is the length of the string. Decryption is exponential in the worst case, depending on the number of valid decryption branches.
Space Complexity: O(k + m) for storing mappings and dictionary, where k is the number of keys and m is the size of the dictionary.
Instead of brute forcing for all possible decryptions, this approach preprocesses the dictionary strings into a Trie structure which allows efficient look-up of potential matches during decryption. This approach attempts to leverage the prefix nature of the Trie to cut down unnecessary branches of exploration.
This C++ solution uses a Trie to store the dictionary for quick lookup. The encryption process is similar to the previous method, however, the decryption leverages the Trie data structure to efficiently count valid dictionary words as it builds potential decryptions by recursively exploring the Trie based on encrypted pairs.
C++
JavaScript
Time Complexity: O(n) for encryption and approximately O(2^m) for decryption in the worst case, where m is the length of word2. The Trie optimizes search by pruning non-matching prefixes.
Space Complexity: O(k + m * l), where l is the average length of dictionary words.
We use a hash table mp to record the encryption result of each character, and another hash table cnt to record the number of occurrences of each encryption result.
In the constructor, we traverse keys and values, storing each character and its corresponding encryption result in mp. Then, we traverse dictionary to count the occurrences of each encryption result. The time complexity is O(n + m), where n and m are the lengths of keys and dictionary, respectively.
In the encryption function, we traverse each character of the input string word1, look up its encryption result, and concatenate them. If a character does not have a corresponding encryption result, it means encryption is not possible, and we return an empty string. The time complexity is O(k), where k is the length of word1.
In the decryption function, we directly return the count of word2 in cnt. The time complexity is O(1).
The space complexity is O(n + m).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Direct Mapping Approach | Time Complexity: Encryption is O(n), where n is the length of the string. Decryption is exponential in the worst case, depending on the number of valid decryption branches. |
| Preprocessed Decryption Approach Using Trie | Time Complexity: O(n) for encryption and approximately O(2^m) for decryption in the worst case, where m is the length of |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Mapping (Hash Map + Dictionary Scan) | Encrypt: O(n), Decrypt: O(D * L) | O(K + D) | Simple implementation when dictionary size is small and decrypt calls are limited. |
| Preprocessed Decryption Using Trie | Encrypt: O(n), Decrypt: O(branch^k) with pruning | O(D * L) | Best when decrypt is called frequently and dictionary words share common prefixes. |
Encrypt and Decrypt Strings | Leetcode 2227 | Range Based Binary Search | Contest 287 🔥🔥 • Coding Decoded • 1,806 views views
Watch 8 more video solutions →Practice Encrypt and Decrypt Strings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor