2227. Encrypt and Decrypt Strings

HardDesignTrieArrayHash TableString
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which technique can we use to find the middle of a linked list?

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.

    1self.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.

    1self.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.

    1res.append(self.mp[c])

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

    1return ''.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.

    1return 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).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

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

1from collections import Counter
2from typing import List
3
4class Encrypter:
5    # Initialize the Encrypter with keys-values mapping and a list of words
6    def __init__(self, keys: List[str], values: List[str], dictionary: List[str]):
7        # Create a map from keys to values
8        self.key_to_value_map = dict(zip(keys, values))
9        # Count how many times each encrypted word appears in the dictionary
10        self.encrypted_word_count = Counter(self.encrypt(word) for word in dictionary)
11
12    # Encrypt a word by mapping each character to its corresponding value
13    def encrypt(self, word1: str) -> str:
14        # Initialize a list to hold the encrypted characters
15        encrypted_chars = []
16        # Go through each character in the input word
17        for char in word1:
18            # If the character does not have a mapping, encryption is not possible
19            if char not in self.key_to_value_map:
20                return ''
21            # Append the mapped value of the character to the list
22            encrypted_chars.append(self.key_to_value_map[char])
23        # Join the encrypted characters into a string and return
24        return ''.join(encrypted_chars)
25
26    # Decrypt an encrypted word by counting how many times it appears in the encrypted dictionary
27    def decrypt(self, word2: str) -> int:
28        # Return the count of how many times the encrypted word appears in the dictionary
29        return self.encrypted_word_count[word2]
30
31# Example usage:
32# keys = ['a', 'b', 'c']
33# values = ['1', '2', '3']
34# dictionary = ['abc', 'def']
35# obj = Encrypter(keys, values, dictionary)
36# encrypted = obj.encrypt('abc')  # Should return the encrypted version of 'abc', e.g. '123'
37# decrypted_count = obj.decrypt('123')  # Should return the number of times '123' appears in the dictionary
38
1import java.util.HashMap;
2import java.util.Map;
3
4// Encrypter class responsible for encryption and decryption
5class Encrypter {
6    // Hash map to store the mapping of characters to strings (encryption keys to their values)
7    private Map<Character, String> keyMap = new HashMap<>();
8    // Hash map to store the count of encrypted words found in the dictionary
9    private Map<String, Integer> encryptedWordCount = new HashMap<>();
10
11    // Constructor that initializes the encrypter with keys, values and a dictionary of words
12    public Encrypter(char[] keys, String[] values, String[] dictionary) {
13        // Populate the keyMap with keys and their corresponding encrypted strings
14        for (int i = 0; i < keys.length; ++i) {
15            keyMap.put(keys[i], values[i]);
16        }
17        // Encrypt each word in the dictionary and update the encryptedWordCount map
18        for (String word : dictionary) {
19            String encrypted = encrypt(word);
20            encryptedWordCount.put(encrypted, encryptedWordCount.getOrDefault(encrypted, 0) + 1);
21        }
22    }
23
24    // Method to encrypt a word using the keyMap
25    public String encrypt(String word) {
26        StringBuilder encryptedWord = new StringBuilder();
27        // For each character in the word, find the encrypted string and append it
28        for (char character : word.toCharArray()) {
29            if (!keyMap.containsKey(character)) {
30                // Return an empty string if a character cannot be encrypted (no mapping found)
31                return "";
32            }
33            encryptedWord.append(keyMap.get(character));
34        }
35        return encryptedWord.toString();
36    }
37
38    // Method to decrypt an encrypted string by finding out how many times it appears in the dictionary
39    public int decrypt(String encryptedWord) {
40        // Return the count of the encrypted word in the dictionary, defaulting to 0 if not found
41        return encryptedWordCount.getOrDefault(encryptedWord, 0);
42    }
43}
44
45// How to use the Encrypter class
46/*
47Encrypter obj = new Encrypter(keys, values, dictionary);
48String encryptedWord = obj.encrypt(word1); // Encrypts the word1 string
49int decryptionCount = obj.decrypt(encryptedWord); // Decrypts and returns the count of how many times the encrypted string appears in the dictionary
50*/
51
1#include <vector>
2#include <string>
3#include <unordered_map>
4
5using namespace std;
6
7// Class Encrypter to handle encryption and decryption of words.
8class Encrypter {
9private:
10    // Data structure to store the count of how many times an encrypted word appears in the dictionary.
11    unordered_map<string, int> encryptedWordCount;
12
13    // Mapping of character to its encrypted string representation.
14    unordered_map<char, string> encryptionMap;
15
16public:
17    // Constructor of the Encrypter class.
18    // Initializes the encryption map using the keys and their corresponding values.
19    // Counts encrypted versions of words in the dictionary.
20    Encrypter(vector<char>& keys, vector<string>& values, vector<string>& dictionary) {
21        for (int i = 0; i < keys.size(); ++i) {
22            encryptionMap[keys[i]] = values[i];
23        }
24
25        for (const auto& word : dictionary) {
26            string encryptedWord = encrypt(word);
27            if (!encryptedWord.empty()) {
28                encryptedWordCount[encryptedWord]++;
29            }
30        }
31    }
32
33    // Encrypts a given word by converting each character to its corresponding encrypted string.
34    string encrypt(string word) {
35        string encryptedWord = "";
36        for (char ch : word) {
37            // If character not found in encryption map, return empty string (invalid encryption).
38            if (!encryptionMap.count(ch)) return "";
39            encryptedWord += encryptionMap[ch];
40        }
41        return encryptedWord;
42    }
43
44    // Decrypts an encrypted word by returning how many times it appeared in the encrypted dictionary.
45    int decrypt(string encryptedWord) {
46        return encryptedWordCount[encryptedWord];
47    }
48};
49
50// Example of how to use the Encrypter class.
51/*
52vector<char> keys = {'a', 'b', 'c'};
53vector<string> values = {"aa", "bb", "cc"};
54vector<string> dictionary = {"abc", "cba"};
55Encrypter* obj = new Encrypter(keys, values, dictionary);
56string param_1 = obj->encrypt("abc");
57int param_2 = obj->decrypt("aabbcc");
58delete obj; // Clean up the allocated object.
59*/
60
1// Importing necessary data structures
2import { Dictionary, Map, Set } from "typescript-collections";
3
4// Global data structures
5let encryptedWordCount: Dictionary<string, number> = new Dictionary<string, number>();
6let encryptionMap: Map<string, string> = new Map<string, string>();
7
8/**
9 * Initializes the encryption map using the keys and their corresponding encrypted values.
10 * Counts encrypted versions of words in the dictionary and updates global data structures.
11 * 
12 * @param keys - array of characters that are keys for encryption
13 * @param values - array of encrypted strings corresponding to each key
14 * @param dictionary - array of words that represents the dictionary to use
15 */
16function initializeEncrypter(keys: string[], values: string[], dictionary: string[]): void {
17    keys.forEach((key, index) => {
18        encryptionMap.setValue(key, values[index]);
19    });
20
21    dictionary.forEach((word) => {
22        const encryptedWord = encrypt(word);
23        if (encryptedWord !== "") {
24            let count = encryptedWordCount.getValue(encryptedWord) || 0;
25            encryptedWordCount.setValue(encryptedWord, count + 1);
26        }
27    });
28}
29
30/**
31 * Encrypts a given word by converting each character to its corresponding encrypted string.
32 * 
33 * @param word - the word to be encrypted
34 * @return - the encrypted word or an empty string if invalid encryption
35 */
36function encrypt(word: string): string {
37    let encryptedWord = "";
38    for (let i = 0; i < word.length; i++) {
39        const ch = word[i];
40        // If character not found in encryption map, return an empty string (invalid encryption)
41        if (!encryptionMap.containsKey(ch)) {
42            return "";
43        }
44        encryptedWord += encryptionMap.getValue(ch);
45    }
46    return encryptedWord;
47}
48
49/**
50 * Decrypts an encrypted word by returning how many times it appeared in the encrypted dictionary.
51 * 
52 * @param encryptedWord - the word to be decrypted
53 * @return - the decryption count
54 */
55function decrypt(encryptedWord: string): number {
56    return encryptedWordCount.getValue(encryptedWord) ?? 0;
57}
58
59/* Example of how to use the global functions.
60const keys = ['a', 'b', 'c'];
61const values = ["aa", "bb", "cc"];
62const dictionary = ["abc", "cba"];
63
64initializeEncrypter(keys, values, dictionary);
65const encrypted = encrypt("abc");
66const decryptionCount = decrypt("aabbcc");
67*/
68
Not Sure What to Study? Take the 2-min Quiz：

Which two pointer techniques do you use to check if a string is a palindrome?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Recommended Readings

Trie Introduction

Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫