Watch 9 video solutions for Encrypt and Decrypt Strings, a hard level problem involving Array, Hash Table, String. This walkthrough by Coding Decoded has 1,806 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |