Encrypt and Decrypt Strings

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 with the following process:

1. For each character c in the string, we find the index i satisfying keys[i] == c in keys.
2. Replace c with values[i] in the string.

Note that in case a character of the string is not present in keys, the encryption process cannot be carried out, and an empty string "" is returned.

A string is decrypted with the following process:

1. For each substring s of length 2 occurring at an even index in the string, we find an i such that values[i] == s. If there are multiple valid i, we choose any one of them. This means a string could have multiple possible strings it can decrypt to.
2. Replace s with keys[i] in the string.

Implement the Encrypter class:

• Encrypter(char[] keys, String[] values, String[] dictionary) Initializes the Encrypter class with keys, values, and dictionary.
• String encrypt(String word1) Encrypts word1 with the encryption process described above and returns the encrypted string.
• int decrypt(String word2) Returns the number of possible strings word2 could decrypt to that also appear in dictionary.

 

Example 1:

Input
["Encrypter", "encrypt", "decrypt"]
[[['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]], ["abcd"], ["eizfeiam"]]
Output
[null, "eizfeiam", 2]

Explanation
Encrypter encrypter = new Encrypter([['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]);
encrypter.encrypt("abcd"); // return "eizfeiam". 
                           // 'a' maps to "ei", 'b' maps to "zf", 'c' maps to "ei", and 'd' maps to "am".
encrypter.decrypt("eizfeiam"); // return 2. 
                              // "ei" can map to 'a' or 'c', "zf" maps to 'b', and "am" maps to 'd'. 
                              // Thus, the possible strings after decryption are "abad", "cbad", "abcd", and "cbcd". 
                              // 2 of those strings, "abad" and "abcd", appear in dictionary, so the answer is 2.

 

Constraints:

• 1 <= keys.length == values.length <= 26
• values[i].length == 2
• 1 <= dictionary.length <= 100
• 1 <= dictionary[i].length <= 100
• All keys[i] and dictionary[i] are unique.
• 1 <= word1.length <= 2000
• 1 <= word2.length <= 200
• All word1[i] appear in keys.
• word2.length is even.
• keys, values[i], dictionary[i], word1, and word2 only contain lowercase English letters.
• At most 200 calls will be made to encrypt and decrypt in total.

SOLUTION:

class Node:
    def __init__(self, val=None, children={}, end=False):
        self.val = val
        self.children = children
        self.end = end

class Trie:
    def __init__(self):
        self.root = Node(val=None, children={})

    def insert(self, word: str) -> None:
        n = len(word)
        curr = self.root
        for i, c in enumerate(word):
            if c in curr.children:
                curr = curr.children[c]
            else:
                newcurr = Node(val=c, children={})
                curr.children[c] = newcurr
                curr = newcurr
        curr.end = True

class Encrypter:

    def __init__(self, keys: List[str], values: List[str], dictionary: List[str]):
        self.trie = Trie()
        for word in dictionary:
            self.trie.insert(word)
        self.encmap = {}
        self.decmap = {}
        n = len(keys)
        for i in range(n):
            self.encmap[keys[i]] = values[i]
            self.decmap[values[i]] = self.decmap.get(values[i], []) + [keys[i]]

    def encrypt(self, word1: str) -> str:
        return "".join([self.encmap[c] for c in word1])

    def decrypt(self, word2: str) -> int:
        n = len(word2)
        ctr = 0
        chunks = [word2[i:i+2] for i in range(0, n, 2)]
        stack = [(self.trie.root, "", 0)]
        while len(stack) > 0:
            curr, currstr, i = stack.pop()
            if i == len(chunks) and curr.end:
                ctr += 1
            if i < len(chunks):
                for nchunk in self.decmap.get(chunks[i], []):
                    if nchunk in curr.children:
                        stack.append((curr.children[nchunk], currstr + nchunk, i + 1))
        return ctr

# Your Encrypter object will be instantiated and called as such:
# obj = Encrypter(keys, values, dictionary)
# param_1 = obj.encrypt(word1)
# param_2 = obj.decrypt(word2)