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:
- For each character
c
in the string, we find the indexi
satisfyingkeys[i] == c
inkeys
. - Replace
c
withvalues[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:
- For each substring
s
of length 2 occurring at an even index in the string, we find ani
such thatvalues[i] == s
. If there are multiple validi
, we choose any one of them. This means a string could have multiple possible strings it can decrypt to. - Replace
s
withkeys[i]
in the string.
Implement the Encrypter
class:
-
Encrypter(char[] keys, String[] values, String[] dictionary)
Initializes theEncrypter
class withkeys, values
, anddictionary
. -
String encrypt(String word1)
Encryptsword1
with the encryption process described above and returns the encrypted string. -
int decrypt(String word2)
Returns the number of possible stringsword2
could decrypt to that also appear indictionary
.
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]
anddictionary[i]
are unique. -
1 <= word1.length <= 2000
-
1 <= word2.length <= 200
- All
word1[i]
appear inkeys
. -
word2.length
is even. -
keys
,values[i]
,dictionary[i]
,word1
, andword2
only contain lowercase English letters. - At most
200
calls will be made toencrypt
anddecrypt
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)
Top comments (0)