2227. Encrypt and Decrypt Strings LeetCode Solution
In this guide, you will get 2227. Encrypt and Decrypt Strings LeetCode Solution with the best time and space complexity. The solution to Encrypt and Decrypt Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 index i satisfying keys[i] == c in keys.
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:
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.
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.
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
2 <= 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.
Complexity Analysis
Time Complexity: O(|\texttt{word2}| + \Sigma |\texttt{dictionary[i]}|)
Space Complexity: O(\Sigma |\texttt{dictionary[i]}|)
2227. Encrypt and Decrypt Strings LeetCode Solution in C++
struct TrieNode {
vector<shared_ptr<TrieNode>> children;
bool isWord = false;
TrieNode() : children(26) {}
};
class Encrypter {
public:
Encrypter(vector<char>& keys, vector<string>& values,
vector<string>& dictionary) {
for (int i = 0; i < keys.size(); ++i) {
const char key = keys[i];
const string& value = values[i];
keyToValue[key] = value;
valueToKeys[value].push_back(key);
}
for (const string& word : dictionary)
insert(word);
}
string encrypt(string word1) {
string ans;
for (const char c : word1)
ans += keyToValue[c];
return ans;
}
int decrypt(string word2) {
return find(word2, 0, root);
}
private:
unordered_map<char, string> keyToValue;
unordered_map<string, vector<char>> valueToKeys;
shared_ptr<TrieNode> root = make_shared<TrieNode>();
void insert(const string& word) {
shared_ptr<TrieNode> node = root;
for (const char c : word) {
const int i = c - 'a';
if (node->children[i] == nullptr)
node->children[i] = make_shared<TrieNode>();
node = node->children[i];
}
node->isWord = true;
}
int find(const string& word, int i, shared_ptr<TrieNode> node) {
const string value = word.substr(i, 2);
if (!valueToKeys.contains(value))
return 0;
int ans = 0;
if (i + 2 == word.length()) {
for (const char key : valueToKeys[value]) {
const auto& child = node->children[key - 'a'];
ans += child && child->isWord;
}
return ans;
}
for (const char key : valueToKeys[value]) {
if (!node->children[key - 'a'])
continue;
ans += find(word, i + 2, node->children[key - 'a']);
}
return ans;
}
}; /* code provided by PROGIEZ */
2227. Encrypt and Decrypt Strings LeetCode Solution in Java
class TrieNode {
public TrieNode[] children = new TrieNode[26];
public boolean isWord = false;
}
class Encrypter {
public Encrypter(char[] keys, String[] values, String[] dictionary) {
for (int i = 0; i < keys.length; ++i) {
final char key = keys[i];
final String value = values[i];
keyToValue.put(key, value);
valueToKeys.putIfAbsent(value, new ArrayList<>());
valueToKeys.get(value).add(key);
}
for (final String word : dictionary)
insert(word);
}
public String encrypt(String word1) {
StringBuilder sb = new StringBuilder();
for (final char c : word1.toCharArray())
sb.append(keyToValue.get(c));
return sb.toString();
}
public int decrypt(String word2) {
return find(word2, 0, root);
}
private Map<Character, String> keyToValue = new HashMap<>();
private Map<String, List<Character>> valueToKeys = new HashMap<>();
private TrieNode root = new TrieNode();
void insert(final String word) {
TrieNode node = root;
for (final char c : word.toCharArray()) {
final int i = c - 'a';
if (node.children[i] == null)
node.children[i] = new TrieNode();
node = node.children[i];
}
node.isWord = true;
}
int find(final String word, int i, TrieNode node) {
final String value = word.substring(i, i + 2);
if (!valueToKeys.containsKey(value))
return 0;
int ans = 0;
if (i + 2 == word.length()) {
for (final char key : valueToKeys.get(value)) {
TrieNode child = node.children[key - 'a'];
if (child != null && child.isWord)
++ans;
}
return ans;
}
for (final char key : valueToKeys.get(value)) {
if (node.children[key - 'a'] == null)
continue;
ans += find(word, i + 2, node.children[key - 'a']);
}
return ans;
}
} // code provided by PROGIEZ
2227. Encrypt and Decrypt Strings LeetCode Solution in Python
class TrieNode:
def __init__(self):
self.children: dict[str, TrieNode] = collections.defaultdict(TrieNode)
self.isWord = False
class Encrypter:
def __init__(self, keys: list[str], values: list[str], dictionary: list[str]):
self.keyToValue = {k: v for k, v in zip(keys, values)}
self.valueToKeys = collections.defaultdict(list)
self.root = TrieNode()
for k, v in zip(keys, values):
self.valueToKeys[v].append(k)
for word in dictionary:
self._insert(word)
def encrypt(self, word1: str) -> str:
return ''.join(self.keyToValue[c] for c in word1)
def decrypt(self, word2: str) -> int:
return self._find(word2, 0, self.root)
def _insert(self, word: str) -> None:
node = self.root
for c in word:
node = node.children.setdefault(c, TrieNode())
node.isWord = True
def _find(self, word: str, i: int, node: TrieNode) -> int:
value = word[i:i + 2]
if value not in self.valueToKeys:
return 0
ans = 0
if i + 2 == len(word):
for key in self.valueToKeys[value]:
ans += node.children[key].isWord
return ans
for key in self.valueToKeys[value]:
if key not in node.children:
continue
ans += self._find(word, i + 2, node.children[key])
return ans # code by PROGIEZ
