LeetCode 2227 - Encrypt and Decrypt Strings

Difficulty: 🔴 Hard
Topics: Array, Hash Table, String, Design, Trie

Solution

Problem Understanding

This problem asks us to implement an Encrypter class that can both encrypt and decrypt strings according to custom character mappings. The keys array provides the characters that can be encrypted, and values provides the corresponding 2-character strings that each key maps to. The encryption of a string is straightforward: each character is replaced by its corresponding 2-character string. Decryption is more challenging because multiple characters could map to the same encrypted string, meaning a single encrypted string can correspond to multiple original strings. Only decrypted strings present in the given dictionary count as valid.

The input constraints guarantee that keys has unique characters and values are all 2-character strings. dictionary contains only unique strings and can be used to filter the valid decrypted results. Maximum lengths are reasonable (keys ≤ 26, dictionary ≤ 100, word lengths ≤ 2000), so we need an efficient way to count all valid decrypted strings, but the total number of calls to encrypt and decrypt is small (≤ 200).

Important edge cases include encrypted strings with collisions (where multiple characters map to the same encrypted value), strings with all characters in keys, and strings that cannot be encrypted because some characters are missing from keys. Another subtle point is that decryption must check only valid dictionary words, not all possible character combinations.

Approaches

The brute-force approach would attempt to generate all possible decrypted strings for a given encrypted string by recursively trying every possible character that maps to each 2-character segment. After generating all possibilities, it would count how many are in the dictionary. This works but is computationally expensive because the number of possibilities grows exponentially with the length of the string, especially if multiple characters map to the same encrypted value.

The optimal approach leverages the small size of the dictionary and precomputes a map from encrypted strings to their count in the dictionary. We encrypt each word in the dictionary once and store the frequency of its encrypted form. Then, when decrypting, instead of exploring all possible original strings, we simply look up how many words in the dictionary could produce the given encrypted string. This reduces decryption from exponential to linear in the length of the encrypted string.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n) worst case for decryption	O(2^n)	Generate all possible decryptions recursively, slow for long strings
Optimal	O(D * L + N)	O(D)	Precompute encrypted dictionary; D = dictionary size, L = avg word length, N = word2 length

Algorithm Walkthrough

Initialize the Encrypter class with three inputs: keys, values, and dictionary.
Build a direct encryption_map from each character in keys to its corresponding 2-character value in values.
Build a reverse decryption_map from each 2-character string in values to a list of characters that could produce it. This is necessary because multiple keys can map to the same encrypted value.
Precompute encrypted_dict_count by encrypting every word in dictionary using encryption_map and counting the frequency of each encrypted result. This allows fast decryption queries.
For the encrypt method, iterate through each character of the input string. If the character exists in encryption_map, append its mapped value; otherwise, return an empty string.
For the decrypt method, simply return the count of the encrypted string in encrypted_dict_count. If not present, return 0.
The core idea is that encryption is deterministic and fast, while decryption is reduced to a dictionary lookup, avoiding exponential enumeration.

Why it works: By precomputing all possible encrypted forms of dictionary words, we guarantee that decrypt counts only valid dictionary words. This ensures correctness even when multiple characters map to the same encrypted string because all collisions are already accounted for in the precomputation.

Python Solution

from typing import List
from collections import defaultdict

class Encrypter:

    def __init__(self, keys: List[str], values: List[str], dictionary: List[str]):
        self.encryption_map = {k: v for k, v in zip(keys, values)}
        self.decryption_map = defaultdict(list)
        for k, v in zip(keys, values):
            self.decryption_map[v].append(k)
        self.encrypted_dict_count = defaultdict(int)
        for word in dictionary:
            encrypted_word = self.encrypt(word)
            if encrypted_word:
                self.encrypted_dict_count[encrypted_word] += 1

    def encrypt(self, word1: str) -> str:
        result = []
        for ch in word1:
            if ch not in self.encryption_map:
                return ""
            result.append(self.encryption_map[ch])
        return "".join(result)

    def decrypt(self, word2: str) -> int:
        return self.encrypted_dict_count.get(word2, 0)

This implementation uses a straightforward hash map for encryption. Precomputing the encrypted forms of dictionary words allows decrypt to run in constant time relative to the number of calls, only paying the upfront cost once.

Go Solution

package main

type Encrypter struct {
    encryptionMap    map[byte]string
    encryptedDictMap map[string]int
}

func Constructor(keys []byte, values []string, dictionary []string) Encrypter {
    em := make(map[byte]string)
    for i, k := range keys {
        em[k] = values[i]
    }

    edm := make(map[string]int)
    for _, word := range dictionary {
        encrypted := ""
        valid := true
        for i := 0; i < len(word); i++ {
            if val, ok := em[word[i]]; ok {
                encrypted += val
            } else {
                valid = false
                break
            }
        }
        if valid {
            edm[encrypted]++
        }
    }

    return Encrypter{
        encryptionMap:    em,
        encryptedDictMap: edm,
    }
}

func (this *Encrypter) Encrypt(word1 string) string {
    res := ""
    for i := 0; i < len(word1); i++ {
        val, ok := this.encryptionMap[word1[i]]
        if !ok {
            return ""
        }
        res += val
    }
    return res
}

func (this *Encrypter) Decrypt(word2 string) int {
    return this.encryptedDictMap[word2]
}

Go-specific notes: Go uses map[byte]string for encryption and map[string]int for storing counts. String concatenation with += is acceptable for small strings; for longer strings, strings.Builder could optimize memory allocation.

Worked Examples

Example Input: "abcd" encrypted with ['a', 'b', 'c', 'd'] → ["ei", "zf", "ei", "am"]

Step through encryption:

Char	Encryption
'a'	"ei"
'b'	"zf"
'c'	"ei"
'd'	"am"

Result: "eizfeiam"

Step through decryption lookup:

Precomputed encrypted_dict_count contains "eizfeiam" → appears 2 times in encrypted dictionary words ("abcd" and "abad").

Answer: 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(D * L + N)	D = dictionary size, L = average word length, N = length of word1 for encryption
Space	O(D)	Store encrypted dictionary counts, plus maps of size ≤ 26 for keys and 26 for values

The preprocessing step dominates the cost. After that, both encrypt and decrypt run in O(N) and O(1) respectively.

Test Cases

keys = ['a', 'b', 'c', 'd']
values = ["ei", "zf", "ei", "am"]
dictionary = ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]

encrypter = Encrypter(keys, values, dictionary)

# Basic encryption test
assert encrypter.encrypt("abcd") == "eizfeiam"  # Maps each char correctly
assert encrypter.encrypt("a") == "ei"           # Single char encryption
assert encrypter.encrypt("z") == ""             # Char not in keys returns empty

# Decryption tests
assert encrypter.decrypt("eizfeiam") == 2       # Two dictionary words decrypt to this
assert encrypter.decrypt("ei") == 0             # No dictionary word is just "ei"
assert encrypter.decrypt("unknown") == 0        # Nonexistent encrypted string

# Edge dictionary words
assert encrypter.encrypt("abad") == "eizam"     # Test mapping with collisions
assert encrypter.decrypt("eizam") == 1

Test	Why
"abcd" encrypt	Valid mapping for all characters
Single character "a"	Simple base case
Nonexistent char "z"	Should return empty string
Decrypt valid encrypted string	Counts dictionary matches correctly
Decrypt string with no dictionary match	Should return 0
Encrypt word with repeated mapping	Handles collisions correctly

Edge Cases

First, when the string contains a character not present in keys, encrypt