How do you solve Encrypt and Decrypt Strings on LeetCode?

Encrypt and Decrypt Strings (LeetCode #2227) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using hash maps allows for O(1) average time complexity for lookups, making both encryption and decryption efficient.

What is the brute force solution for Encrypt and Decrypt Strings?

The brute force approach for Encrypt and Decrypt Strings is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we will iterate through each character of the input string and find its corresponding encrypted value using a simple loop. For decryption, we will check every possible substring of length 2 to see if it matches any value in the dictionary. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Encrypt and Decrypt Strings?

Encrypt and Decrypt Strings uses the following concepts: Array, Hash Table, String, Design, Trie. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Encrypt and Decrypt Strings?

Always clarify the problem requirements and constraints before jumping into coding. Think about edge cases, such as empty strings or characters not in the keys, and how they affect your solution. Practice explaining your thought process as you code; this helps interviewers understand your reasoning.

What are common mistakes when solving Encrypt and Decrypt Strings?

Failing to handle characters not present in the keys during encryption, leading to incorrect results. Not considering the case where the length of the encrypted string is odd during decryption, which can lead to errors.

#2227

Encrypt and Decrypt Strings

Hard

ArrayHash TableStringDesignTrieHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution leverages hash maps for quick lookups during encryption and decryption, ensuring that we can efficiently find the corresponding values or keys without unnecessary iterations.

⚙️

Algorithm

3 steps

1Step 1: Create a mapping from each character in keys to its corresponding value in values and vice versa using two hash maps.
2Step 2: For encryption, iterate through the input string and replace each character using the mapping. If a character is not found, return an empty string immediately.
3Step 3: For decryption, check every two-character substring in the encrypted string. Use the reverse mapping to find possible original characters and count how many valid combinations exist in the dictionary.

solution.py28 lines

1class Encrypter:
2    def __init__(self, keys, values, dictionary):
3        self.map = {keys[i]: values[i] for i in range(len(keys))}
4        self.reverse_map = {values[i]: keys[i] for i in range(len(values))}
5        self.dictionary = set(dictionary)
6
7    def encrypt(self, word1):
8        encrypted = []
9        for char in word1:
10            if char in self.map:
11                encrypted.append(self.map[char])
12            else:
13                return ""
14        return ''.join(encrypted)
15
16    def decrypt(self, word2):
17        count = 0
18        n = len(word2)
19        if n % 2 != 0:
20            return 0
21        possible_decryptions = set()
22        for i in range(0, n, 2):
23            if word2[i:i+2] in self.reverse_map:
24                possible_decryptions.add(self.reverse_map[word2[i:i+2]])
25        for original in possible_decryptions:
26            if original in self.dictionary:
27                count += 1
28        return count

ℹ

Complexity note: The time complexity is O(n) because we only iterate through the input string a limited number of times, and lookups in the hash maps are O(1). The space complexity is O(n) due to the storage of the mappings and the dictionary.

1Using hash maps allows for O(1) average time complexity for lookups, making both encryption and decryption efficient.
2Understanding the relationship between keys and values is crucial for both processes, as they are directly tied to how we encrypt and decrypt strings.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.