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.
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:
For encryption, follow the instruction. Time complexity: O(len(word)) = O(2000)
For decryption, try all words in the dictionary and encrypt them and compare the encrypted string with the word to decrypt. Time complexity: O(sum(len(word_in_dict))) = O(100*100)
Worst case: 200 calls to decryption, T = 200 * O(100 * 100) = O(2*106)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Author: Huahua class Encrypter { public: Encrypter(vector<char>& keys, vector<string>& values, vector<string>& dictionary): vals(26), dict(dictionary) { for (size_t i = 0; i < keys.size(); ++i) vals[keys[i] - 'a'] = values[i]; } string encrypt(string word1) { string ans; for (char c : word1) ans += vals[c - 'a']; return ans; } int decrypt(string word2) { return count_if(begin(dict), end(dict), [&](const string& w){ return encrypt(w) == word2; }); } private: vector<string> vals; vector<string> dict; }; |
Optimization
Pre-compute answer for all the words in dictionary.
decrypt: Time complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Author: Huahua class Encrypter { public: Encrypter(vector<char>& keys, vector<string>& values, vector<string>& dictionary): vals(26) { for (size_t i = 0; i < keys.size(); ++i) vals[keys[i] - 'a'] = values[i]; for (const string& w : dictionary) ++counts[encrypt(w)]; } string encrypt(string word1) { string ans; for (char c : word1) ans += vals[c - 'a']; return ans; } int decrypt(string word2) { auto it = counts.find(word2); return it == counts.end() ? 0 : it->second; } private: vector<string> vals; unordered_map<string, int> counts; }; |