2227. Encrypt and Decrypt Strings

On LeetCode ->

class Encrypter:

    def __init__(self, keys: list[str], values: list[str], dictionary: list[str]):
        pass

    def encrypt(self, word1: str) -> str:
        pass

    def decrypt(self, word2: str) -> int:
        pass

Problem¶

Build an encrypter that replaces each character with its assigned two-character code.

encrypt(word1) returns the encoded string, or "" if a character has no mapping.
decrypt(word2) counts dictionary words whose encryption equals word2.

keys       = ["a", "b", "c"]
values     = ["xy", "zz", "xy"]
dictionary = ["ab", "cb", "aa", "d"]

encrypt("ab")   -> "xyzz"
encrypt("d")    -> ""
decrypt("xyzz") -> 2       # "ab" and "cb"
decrypt("xyxy") -> 1       # only "aa" is in the dictionary

Key trick¶

Encrypt every dictionary word once and count the resulting ciphertexts; decryption becomes a frequency lookup rather than a search.

Trap¶

Different characters can share a code, so encryption is not invertible; also, skip dictionary words containing unmapped characters instead of counting their failed encryption.

Why is it interesting?¶

It turns an ambiguous inverse problem into a simple forward computation by exploiting the small, fixed dictionary.

Python solution¶

class Encrypter:
    def __init__(self, keys: list[str], values: list[str], dictionary: list[str],):
        self.codes = dict(zip(keys, values))
        self.counts = {}

        for word in dictionary:
            encrypted = self.encrypt(word)
            # Dictionary words are nonempty, so "" means encryption failed.
            if encrypted:
                self.counts[encrypted] = self.counts.get(encrypted, 0) + 1

    def encrypt(self, word1: str) -> str:
        parts = []
        for ch in word1:
            code = self.codes.get(ch)
            if code is None:
                return ""
            parts.append(code)
        return "".join(parts)

    def decrypt(self, word2: str) -> int:
        # Count dictionary matches without generating possible originals.
        return self.counts.get(word2, 0)

Let \(K\) be the number of keys, \(D\) the total dictionary characters, \(L\) the plaintext length, and \(C\) the ciphertext length.

Initialization: \(O(K + D)\) time and stored space.
encrypt: \(O(L)\) time and auxiliary space.
decrypt: \(O(C)\) time to hash the input string, followed by an expected \(O(1)\) lookup; \(O(1)\) auxiliary space.

Comment on my solution¶

Your trie-backed DFS is correct: following trie edges ensures every explored prefix belongs to a dictionary word, contrary to your initial concern.

Its search is bounded by the dictionary trie, not unrestricted exponential branching, but every query repeats traversal and checks candidate characters. Precomputing ciphertext counts moves that work to initialization and eliminates recursive searches.

# Ideas:
# - In decrypt as we're counting valid string path, use DP on string prefixes
#   - It seems that the dictionary check for valid string decryption
#     don't let us use DP (at least directly)
#     - maybe we could use also a trie (convert the dictionary into a trie)
#       that we advance with the DP array construction
#       - so that we can just check the last decrypted character
#     - No this won't work because we are going to append character
#       to previous prefix that don't build a correct word in dictionary,
#       and we won't know
# - Use backtracking
#   - maybe with and trie that advance along with the recursion
#     to only consider path that might be valid word (and so prune
#     wrong path)

# WORKS
# But very slow - test run on 2000ms compared to 100ms for
# other people on Leetcode
class Encrypter:

    def __init__(self, keys: list[str], values: list[str], dictionary: list[str]):
        # keys are unique and values can contain duplicate
        self.keys = {ch: values[i] for i, ch in enumerate(keys)}
        self.values = {}
        for i, s in enumerate(values):
            self.values.setdefault(s, []).append(keys[i])
        self.dictionary = {}
        for word in dictionary:
            node = self.dictionary
            for ch in word:
                node = node.setdefault(ch, {})
            node[""] = True # this is a word


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


    def decrypt(self, word2: str) -> int:
        n = len(word2)
        if n % 2:
            return 0

        cnt = 0

        def dfs(i, parent):
            nonlocal cnt
            if i == n:
                if parent.get("", False):
                    cnt += 1
                return
            s = word2[i:i+2]
            for ch in self.values.get(s, []):
                if ch not in parent:
                    continue
                dfs(i+2, parent[ch])

        dfs(0, self.dictionary)

        return cnt