We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Encrypt and Decrypt Strings

Number: 1433

Difficulty: Hard

Paid? No

Companies: Duolingo

Problem Description

Design a data structure that supports encryption and decryption of strings using a given mapping between characters and two-letter strings. The encryption replaces each character with its corresponding two-letter string. Decryption, however, is ambiguous since multiple original characters might map to the same encrypted value. In addition, only those original strings that appear in a provided dictionary are considered valid when decrypting.

Key Insights

  • Use a mapping (hash table) from each character (from keys) to its corresponding two-letter string (from values) for quick encryption.
  • Build a reverse lookup mapping from each two-letter string (encrypted representation) to the possible list or set of characters that could be decrypted.
  • Precompute the encrypted versions of all dictionary words so that on decryption queries you can easily count how many dictionary words match the queried encrypted string without exploring all decryption possibilities.
  • During encryption, if any letter in the word is missing from the keys-to-values mapping, return an empty string.
  • The precomputation helps convert an otherwise exponential decryption problem into a simple lookup.

Space and Time Complexity

Time Complexity:

  • Constructor: O(n * l) where n is the number of dictionary words and l is the average length of each word (to compute their encryptions).
  • Encryption: O(m) for a word of length m.
  • Decryption: O(1) per query (after precomputation).

Space Complexity:

  • O(n) for storing the precomputed dictionary mapping from encrypted strings to counts.
  • O(k) for storing mapping between keys and values, where k is the number of unique keys.

Solution

The solution involves storing two main mappings:

  1. A mapping from characters to their corresponding encrypted string (from keys to values).
  2. A mapping from the encrypted string of a dictionary word (computed using the first mapping) to the count of valid dictionary words that have that encryption.

The encryption function processes each character in the input word, translating it to its corresponding two-letter string. If any character is missing in the mapping, an empty result is returned.

The decryption function simply looks up the count of dictionary words that were precomputed to match the given encrypted string. This avoids trying to compute all possible decryption paths.

This approach is efficient given the constraints and leverages precomputation to reduce the complexity encountered during decryption.

Code Solutions

# Python implementation

class Encrypter:
    def __init__(self, keys, values, dictionary):
        # Map each character to its encrypted two-letter string.
        self.char_to_val = {ch: val for ch, val in zip(keys, values)}
        # Precompute encryption for each word in the dictionary.
        self.encrypted_count = {}
        for word in dictionary:
            encrypted_word = self.encrypt(word)
            # Only consider words that can be fully encrypted.
            if encrypted_word != "":
                self.encrypted_count[encrypted_word] = self.encrypted_count.get(encrypted_word, 0) + 1

    def encrypt(self, word1):
        # Encrypt each character in the string.
        result = []
        for ch in word1:
            # If character not found, encryption cannot be done.
            if ch not in self.char_to_val:
                return ""
            result.append(self.char_to_val[ch])
        return "".join(result)

    def decrypt(self, word2):
        # Lookup the count of dictionary words matching the encrypted string.
        return self.encrypted_count.get(word2, 0)

# Example usage:
# encrypter = Encrypter(['a','b','c','d'], ["ei","zf","ei","am"], ["abcd","acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"])
# print(encrypter.encrypt("abcd"))
# print(encrypter.decrypt("eizfeiam"))
← Back to All Questions