Problem Description

In this LeetCode problem, we are asked to design a data structure that can perform encryption and decryption operations on strings. The key components of this problem involve a keys array that contains unique characters, a values array where each element is a string of length 2, and a dictionary array with permissible original strings after decryption.

Encryption Process:

1. For each character 'c' in the string, find the index 'i' where keys[i] == c.
2. Replace 'c' with values[i].

*If a character in the string does not exist in keys, encryption cannot be done, and an empty string is returned.

Decryption Process:

1. For each even-indexed substring 's' of length 2 in the string, find an index 'i' where values[i] == s.
2. Replace 's' with keys[i].

Decryption may have multiple valid outputs if multiple keys map to the same value.

We must implement an Encrypter class that initializes with keys, values, and dictionary. The class should provide methods for encryption and decryption as described above. The encrypt method encrypts a single string, while decrypt counts how many possible decrypted strings appear in the dictionary.

Intuition

The intuition behind the solution is to use a mapping and frequency counting to efficiently perform the encryption and decryption tasks. The encryption is straightforward: we create a map (mp) from keys to values permitting quick lookups during the encryption process. If a character from the input string is not in keys, return an empty string, indicating encryption is impossible.

For decryption, we count the frequency of all possible encryptions of words in the dictionary, which is done by encrypting each word in the dictionary and storing frequencies in a Counter object (cnt). Decryption of a given string then involves simply returning the count of that string in cnt. This takes advantage of the fact that all valid decryption outputs must match a word in the encrypted dictionary, and multiple encryptions can lead to the same string. Therefore, we use this frequency map to find out how many dictionary words could encrypt to match the given encrypted string, fulfilling the requirements of the decryption process.

By using a map for encryption and a counter for decryption frequencies, we optimize our data structure for the required operations, arriving at a solution that requires initialization to be linear in the size of the dictionary but then allows constant-time encryption and constant-time decryption (decryption time is constant with respect to the length of the decrypted word; it will, of course, vary depending on the number of words in the dictionary).

Learn more about Trie patterns.

Solution Approach

To tackle this problem, the solution employs a hash map and counter strategy alongside a class-based object-oriented approach. The Python code uses data structures like dictionaries and the Counter class from the collections module. It includes an implementation of an Encrypter class, which encapsulates the encryption and decryption logic. Let's dive deeper into the implementation steps.

First, during the instantiation of the Encrypter (__init__ method), two key tasks are performed:

1. A mapping (self.mp) is created by zipping together the keys and values lists. This allows quick and direct lookups for the encryption process. In Python, this is done using the built-in zip function and converting the paired tuples into a dictionary.

   self.mp = dict(zip(keys, values))

   Each 'key' in keys gets associated with a corresponding 'value' in values, forming a key-value pair that will be used in encryption.

2. Secondly, the solution prepares for future decryptions by counting how often each word in the dictionary could be encrypted. This is done by encrypting every word in the dictionary using the created map and then using the Counter to track the frequency of each encrypted word.

   self.cnt = Counter(self.encrypt(v) for v in dictionary)

   This step pre-calculates and stores the encryption outcomes, preparing for an efficient decryption process.

The encrypt method:

1. An empty list res is initialized to store the result of encryption. For each character 'c' in word1, the method checks if 'c' is present in the mapping self.mp. If not found, it returns an empty string indicating failure.

2. If the character is found, its encrypted value (from self.mp) is appended to the res list.

   res.append(self.mp[c])

3. After processing all characters, the list res is joined into a single string, representing the fully encrypted word.

   return ''.join(res)

The decrypt method:

1. Since the encrypt method is called over the dictionary during initialization to track the frequency of each possible encryption, the decrypt method just needs to return the count of the encrypted word2 from the cnt Counter. This is a straightforward lookup that returns how many dictionary words can encrypt to word2.

   return self.cnt[word2]

This solution utilizes a map for constant-time lookups during encryption and a pre-computed frequency counter for constant-time lookups during decryption. The time complexity for the initialization is O(n * m), where 'n' is the number of words in the dictionary and 'm' is the average length of these words due to encryption of each word. Both the encrypt and decrypt functions operate in O(p) time, where 'p' is the length of the input word to be encrypted or decrypted (though, as previously noted, the time for decryption does not depend on the input word's length but rather on the dictionary's precomputed state).

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we are given the following inputs:

• keys = ['a', 'b', 'c']
• values = ['aa', 'bb', 'cc']
• dictionary = ['abc', 'cab', 'bac']

First, we initialize the Encrypter object with these arrays. During the initialization, two main tasks are executed:

1. A mapping (self.mp) is created from keys to values:

   • a -> aa
   • b -> bb
   • c -> cc

2. The solution then encrypts every word in the dictionary and counts the frequency of these encrypted words using a Counter (self.cnt):

   • abc encrypts to aabbcc (frequency tallied)
   • cab encrypts to ccaabb (frequency tallied)
   • bac encrypts to bbaacc (frequency tallied)

Let's follow the encrypt function process with a word, say abc. The encrypt function will operate as follows:

1. Check if each character is in the mapping:

   • 'a' is in the mapping, convert it to 'aa'
   • 'b' is in the mapping, convert it to 'bb'
   • 'c' is in the mapping, convert it to 'cc'

2. Append each encrypted value to the result list res:

   • res = ['aa', 'bb', 'cc']

3. Join the list into a single string:

   • Encrypted string is 'aabbcc'

Next, let's look at the decrypt function, using the string aabbcc. Since all possible encryptions have already been counted, the decrypt function will:

1. Return the count of aabbcc in the cnt Counter, which is 1, since abc is the only word in our dictionary that encrypts to aabbcc.

This way, we have employed maps for efficient encryption lookups and frequency counting for quick decryption results.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__ method: The time complexity of initializing the Encrypter object is O(n * k + m * l), where n is the length of keys, k is the average length of the strings in values, m is the size of the dictionary, and l is the average length of the strings in dictionary. The zip operation takes O(n) and constructing the dictionary self.mp is also O(n) since it involves mapping each of n keys to corresponding values. For the counter creation, it takes O(m * l * k) since for each word in the dictionary with an average length l, the encrypt method is called, which has a time complexity of O(l * k) because for each character in the word, the encryption looks up the corresponding string which has an average length of k.

• encrypt method: The time complexity for the encrypt method is O(l * k) where l is the length of word1 being encrypted and k is the average length of the strings in values. This is because for each character in word1, the method appends the corresponding string from self.mp to the result list, which takes O(k) for each of l characters.

• decrypt method: The decrypt method has a time complexity of O(1) because it performs a simple dictionary lookup on self.cnt to find the count of occurrences of the encrypted string word2.

Space Complexity:

• __init__ method: The space complexity of initializing the Encrypter is O(n * k + m * p), where n is the length of keys, k is the average length of the strings in values, m is the size of the dictionary, and p is the space complexity for storing the encrypted string which is the product of the average length of the strings in dictionary and the average length of the strings in values. The space is used for storing the mapping dictionary self.mp and the counter self.cnt. The self.mp dictionary takes O(n * k) space and self.cnt takes O(m * p) space accounting for all unique encrypted strings with their counts.

• encrypt method: The space complexity for the encrypt method is O(l * k), dominated by the space for the resulting encrypted string, where l is the length of word1 and k is the average length of strings in values.

• decrypt method: Since the decrypt method does not utilize any additional space other than the input and the value lookup, its space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.