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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Encrypt and Decrypt Strings

Difficulty: Hard

Problem Description

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 by replacing each character in the string based on a mapping defined by the keys and values arrays. If a character is not present in keys, the encryption cannot be carried out. Decryption involves finding possible original strings for a given encrypted string from the dictionary.

Key Insights

  • Each character in the input string corresponds to a unique encoded string of length 2.
  • The encryption process relies on the mapping defined by the keys and values arrays.
  • The decryption process involves checking all possible combinations of mappings for substrings of length 2.
  • A dictionary helps in filtering the valid decrypted strings.
  • Efficient data structures like dictionaries (hash maps) can speed up lookups.

Space and Time Complexity

Time Complexity: O(n + m * k), where n is the length of the string being encrypted or decrypted, m is the number of strings in the dictionary, and k is the average number of possible mappings for each substring during decryption.

Space Complexity: O(1) for the encryption (since the output size is proportional to input size), and O(m) for the dictionary storage.

Solution

To solve the problem, we will use the following approach:

  1. Data Structure Initialization: Create a mapping from characters in keys to their corresponding values, and a reverse mapping from values to keys. Also, store the dictionary for quick lookup.

  2. Encryption: For each character in the input string, find its corresponding value using the mapping. If a character is not found, return an empty string. Concatenate the results to form the encrypted string.

  3. Decryption: For the encrypted string, iterate over substrings of length 2 at even indices. For each substring, check the reverse mapping to determine possible original characters. Count the valid combinations that match any string in the dictionary.

Code Solutions

class Encrypter:
    def __init__(self, keys, values, dictionary):
        self.map_encrypt = {keys[i]: values[i] for i in range(len(keys))}
        self.map_decrypt = {}
        for i in range(len(values)):
            if values[i] not in self.map_decrypt:
                self.map_decrypt[values[i]] = []
            self.map_decrypt[values[i]].append(keys[i])
        self.dictionary = set(dictionary)

    def encrypt(self, word1):
        result = []
        for char in word1:
            if char in self.map_encrypt:
                result.append(self.map_encrypt[char])
            else:
                return ""
        return ''.join(result)

    def decrypt(self, word2):
        if len(word2) % 2 != 0:
            return 0
        
        from itertools import product
        
        possible_decrypts = []
        for i in range(0, len(word2), 2):
            sub = word2[i:i+2]
            if sub in self.map_decrypt:
                possible_decrypts.append(self.map_decrypt[sub])
            else:
                return 0
        
        count = 0
        for combination in product(*possible_decrypts):
            decrypted_string = ''.join(combination)
            if decrypted_string in self.dictionary:
                count += 1
        return count
← Back to All Questions