2227. Encrypt and Decrypt Strings - Detailed Explanation

Problem Statement

Design an encryption and decryption system. You are given:

• An array of keys (characters) that can be encrypted.
• An array of values (strings) representing the encrypted mapping for each key.
• A dictionary (list of strings) that contains valid words.

You need to implement an Encrypter class that supports the following operations:

• encrypt(word):
  Convert the given word into an encrypted string by replacing each character with its corresponding mapped value.

• decrypt(word):
  Return the number of words in the dictionary that, when encrypted using the same mapping, equal the given encrypted string.

Note:
Since the encryption mapping might not be one-to-one (i.e., multiple characters may map to the same value), decryption is ambiguous. To resolve this efficiently, you can precompute the encrypted form of each word in the dictionary and count how many times each encrypted result appears.

Hints

1. Mapping for Encryption:
   Build a hash map (or dictionary) that maps each character from the keys array to its corresponding string from the values array. This provides O(1) lookup during encryption.

2. Preprocessing the Dictionary:
   Since decryption might be ambiguous, precompute the encrypted form for every word in the dictionary using the encryption mapping. Store the frequency of each encrypted string in a hash map. Then, decryption simply becomes a lookup in this frequency map.

3. Handling Missing Mappings:
   Decide how to handle cases where a character in a word is not present in the mapping. Typically, the problem ensures that only valid characters are used, but you might need to account for this scenario.

Approaches

Brute Force (Not Recommended)

• Idea:
  For decryption, try to generate all possible original words from the encrypted string using all possible inverse mappings and check which ones are in the dictionary.

• Drawback:
  This approach is computationally expensive because the number of possibilities can be exponential.

Optimal Approach: Precompute Dictionary Encryption

• Encryption:
  For each character in the input word, use the mapping to generate the encrypted string. This operation is O(L), where L is the length of the word.

• Decryption:
  Precompute and store the encrypted form of every word in the dictionary along with its frequency. Then, for each decryption query, simply return the frequency count from this precomputed map. This makes decryption an O(1) operation.

Complexity Analysis

• Encryption:

  • Time Complexity: O(L) per call, where L is the length of the word.
  • Space Complexity: O(L) for constructing the encrypted string.

• Decryption:

  • Time Complexity: O(1) per call (using a frequency lookup).
  • Space Complexity: O(D) where D is the number of words in the dictionary (to store encrypted strings and their counts).

Python Code