2227. Encrypt and Decrypt Strings - Detailed Explanation

Problem Statement

You are asked to design a system that can encrypt and decrypt strings using a given mapping. In this system, you are provided with:

• An array of keys (characters)
• An array of values (strings) that represent the encryption of the corresponding key
• A dictionary of words

You must implement an Encrypter class with the following functions:

• encrypt(word): Encrypts the given word by replacing each character with its corresponding value from the mapping and concatenating the results.

• decrypt(word): Returns the number of words in the dictionary that, when encrypted with the same mapping, match the provided encrypted string.

Example 1

Input:

• keys = ["a", "b", "c", "d"]
• values = ["ei", "zf", "ei", "am"]
• dictionary = ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]
• encrypt("abcd")
• decrypt("eizfeiam")

Output:

• encrypt("abcd") returns "eizfeiam"
• decrypt("eizfeiam") returns 2

Explanation:
When encrypting "abcd":

• 'a' → "ei"
• 'b' → "zf"
• 'c' → "ei"
• 'd' → "am"
  Concatenating these gives "eizfeiam". In the dictionary, exactly 2 words encrypt to "eizfeiam".

Example 2

Input:

• keys = ["a", "b", "c", "d"]
• values = ["ei", "zf", "ei", "am"]
• dictionary = ["a", "b", "c", "d"]
• encrypt("a")
• decrypt("ei")

Output:

• encrypt("a") returns "ei"
• decrypt("ei") returns 2

Explanation:
Both 'a' and 'c' map to "ei", so in the dictionary, if both "a" and "c" are present, decrypt("ei") will count both.

Example 3

Input:

• keys = ["x", "y"]
• values = ["ab", "cd"]
• dictionary = ["xy", "yx", "xx", "yy"]
• encrypt("xy")
• decrypt("abcd")

Output:

• encrypt("xy") returns "abcd"
• decrypt("abcd") returns 1

Explanation:
Encrypting "xy":

• 'x' → "ab"
• 'y' → "cd"
  Concatenation gives "abcd". Only the dictionary word "xy" encrypts to "abcd".

Constraints

• The lengths of keys and values are the same.
• Each key is a lowercase letter and the corresponding value is a string.
• The dictionary may contain many words, and words consist only of lowercase letters.
• It is possible that different keys map to the same value, which creates ambiguity during decryption.

Hints

1. Mapping and Encryption:
   Start by implementing a simple mapping from each key to its value. When encrypting, iterate over the characters of the word and build the encrypted string using this mapping.

2. Preprocessing the Dictionary:
   Since decryption requires finding how many dictionary words match the encrypted string, consider preprocessing the dictionary. Encrypt every dictionary word once, store the result and count the frequency. Then, decryption is simply a lookup.

Approach 1: Brute Force

Explanation

A naive method for decryption would be:

• For the given encrypted string, consider all possible original characters that could map to each segment of the string.

• Use a recursive or DFS (depth-first search) approach to generate all potential original strings.

• For each generated string, check if it exists in the dictionary.

• Count all valid words that match.

Drawbacks

• Exponential Time: When multiple keys map to the same value, the number of possible strings grows exponentially with the length of the word.
• Inefficient for Large Dictionaries: Even a moderate length string might result in an enormous number of possibilities, making this approach impractical.

Approach 2: Optimal Preprocessing

Explanation

The optimal solution takes advantage of precomputation:

1. Encryption Mapping: Create a dictionary (hash map) that maps each key to its corresponding value.

2. Dictionary Preprocessing:

   • For every word in the dictionary, compute its encrypted form using the mapping.

   • Store the result in another hash map where the key is the encrypted string and the value is the frequency (count) of dictionary words that produce this encryption.

3. Encrypt Function:

   • For a given word, simply replace each character using the mapping and concatenate the result.

4. Decrypt Function:

   • For a given encrypted string, perform a lookup in the precomputed map and return the frequency (or 0 if not found).

Benefits

• Fast Lookups: Both encryption and decryption become very fast (O(n) for encryption and O(1) for decryption on average, where n is the length of the word).

• Avoids Exponential Complexity: By preprocessing the dictionary, we do not need to generate all possible original strings.

Step-by-Step Walkthrough and Visual Example

Consider Example 1:

• Mapping:

  • 'a' → "ei"
  • 'b' → "zf"
  • 'c' → "ei"
  • 'd' → "am"

• Encrypting "abcd":

  • 'a' → "ei"
  • 'b' → "zf"
  • 'c' → "ei"
  • 'd' → "am"
  • Concatenated result: "eizfeiam"

• Preprocessing the Dictionary:
  For each word in the dictionary (e.g., "abcd", "acbd", ...), compute its encryption and update the frequency count.
  For instance, if "abcd" and "adbc" both encrypt to "eizfeiam", then in the precomputed map, "eizfeiam" → 2.

• Decrypting "eizfeiam":

  • Simply look up "eizfeiam" in the precomputed map and return the count (2 in this case).

Python Code