{x}
blog image

Encrypt and Decrypt Strings

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:

  1. For each character c in the string, we find the index i satisfying keys[i] == c in keys.
  2. Replace 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:

  1. For each substring 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.
  2. Replace 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 <= 26
  • values[i].length == 2
  • 1 <= dictionary.length <= 100
  • 1 <= dictionary[i].length <= 100
  • All keys[i] and dictionary[i] are unique.
  • 1 <= word1.length <= 2000
  • 2 <= word2.length <= 200
  • All word1[i] appear in keys.
  • word2.length is even.
  • keys, values[i], dictionary[i], word1, and word2 only contain lowercase English letters.
  • At most 200 calls will be made to encrypt and decrypt in total.

Solution Explanation

This problem involves designing an Encrypter class that handles encryption and decryption of strings based on provided keys and values. The solution utilizes hash maps (or dictionaries in Python) for efficient lookups during both encryption and decryption.

Encryption

The encryption process maps each character in the input string to its corresponding value from the values array, based on the index of the character in the keys array. If a character is not found in keys, an empty string is returned. This is implemented using a simple iteration through the input string and lookup in the hash map.

Decryption

Decryption is more complex. It involves iterating through the encrypted string in steps of 2 (because each encrypted character represents two characters in the original string) and looking up each substring of length 2 in the hash map to find the corresponding key. The number of possible decrypted strings that are also present in the dictionary is then returned. This requires building a hash map of encrypted strings to their counts from the dictionary in the constructor.

Time and Space Complexity Analysis

Constructor:

  • Time Complexity: O(K + V + D*L), where K is the length of keys, V is the length of values, D is the length of dictionary, and L is the average length of a string in dictionary. This is due to the iterations to build the encryption map and the count map for decrypted strings.
  • Space Complexity: O(K + V + D), where K is the length of keys, V is the length of values, and D is the length of dictionary. This is the space used to store the encryption map and the decryption counts.

encrypt method:

  • Time Complexity: O(W), where W is the length of word1. This is due to iterating through the input string.
  • Space Complexity: O(W), where W is the length of word1 in the worst case, to store the encrypted string.

decrypt method:

  • Time Complexity: O(1) on average. Accessing the count of a particular encrypted string from the cnt map is O(1) on average.
  • Space Complexity: O(1).

Code Explanation (Python)

The Python code uses collections.Counter to efficiently count the occurrences of encrypted strings in the dictionary. The encrypt method handles character mapping and returns an empty string if a character is not found. The decrypt method directly returns the count of the given encrypted string from the pre-computed cnt dictionary.

Code Explanation (Java, C++, Go)

The Java, C++, and Go code implements similar logic using built-in hash maps. The encrypt and decrypt methods follow the algorithm described above. The constructor preprocesses the dictionary to create a hash map of encrypted strings and their counts in the dictionary.

The efficiency of the solution stems from using hash maps for fast lookups, allowing for O(1) average-case time complexity for the core operations in the encrypt and decrypt methods. The pre-computation in the constructor saves time during the decrypt calls.