| comments | difficulty | edit_url | rating | source | tags | |||||
|---|---|---|---|---|---|---|---|---|---|---|
true |
困难 |
1944 |
第 287 场周赛 Q4 |
|
给你一个字符数组 keys ，由若干 互不相同 的字符组成。还有一个字符串数组 values ，内含若干长度为 2 的字符串。另给你一个字符串数组 dictionary ，包含解密后所有允许的原字符串。请你设计并实现一个支持加密及解密下标从 0 开始字符串的数据结构。
字符串 加密 按下述步骤进行：
- 对字符串中的每个字符
c，先从keys中找出满足keys[i] == c的下标i。 - 在字符串中，用
values[i]替换字符c。
请注意，如果 keys 中不存在字符串中的字符，则无法执行加密过程，返回空字符串 ""。
字符串 解密 按下述步骤进行：
- 将字符串每相邻 2 个字符划分为一个子字符串，对于每个子字符串
s，找出满足values[i] == s的一个下标i。如果存在多个有效的i，从中选择 任意 一个。这意味着一个字符串解密可能得到多个解密字符串。 - 在字符串中，用
keys[i]替换s。
实现 Encrypter 类：
Encrypter(char[] keys, String[] values, String[] dictionary)用keys、values和dictionary初始化Encrypter类。String encrypt(String word1)按上述加密过程完成对word1的加密，并返回加密后的字符串。int decrypt(String word2)统计并返回可以由word2解密得到且出现在dictionary中的字符串数目。
示例：
输入：
["Encrypter", "encrypt", "decrypt"]
[[['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]], ["abcd"], ["eizfeiam"]]
输出：
[null, "eizfeiam", 2]
解释：
Encrypter encrypter = new Encrypter([['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]);
encrypter.encrypt("abcd"); // 返回 "eizfeiam"。
// 'a' 映射为 "ei"，'b' 映射为 "zf"，'c' 映射为 "ei"，'d' 映射为 "am"。
encrypter.decrypt("eizfeiam"); // return 2.
// "ei" 可以映射为 'a' 或 'c'，"zf" 映射为 'b'，"am" 映射为 'd'。
// 因此，解密后可以得到的字符串是 "abad"，"cbad"，"abcd" 和 "cbcd"。
// 其中 2 个字符串，"abad" 和 "abcd"，在 dictionary 中出现，所以答案是 2 。
提示：
1 <= keys.length == values.length <= 26values[i].length == 21 <= dictionary.length <= 1001 <= dictionary[i].length <= 100- 所有
keys[i]和dictionary[i]互不相同 1 <= word1.length <= 20001 <= word2.length <= 200- 所有
word1[i]都出现在keys中 word2.length是偶数keys、values[i]、dictionary[i]、word1和word2只含小写英文字母- 至多调用
encrypt和decrypt总计200次
我们用一个哈希表
在构造函数中，我们遍历
在加密函数中，我们遍历输入字符串
在解密函数中，我们直接返回
空间复杂度
class Encrypter:
def __init__(self, keys: List[str], values: List[str], dictionary: List[str]):
self.mp = dict(zip(keys, values))
self.cnt = Counter(self.encrypt(v) for v in dictionary)
def encrypt(self, word1: str) -> str:
res = []
for c in word1:
if c not in self.mp:
return ''
res.append(self.mp[c])
return ''.join(res)
def decrypt(self, word2: str) -> int:
return self.cnt[word2]
# 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)class Encrypter {
private Map<Character, String> mp = new HashMap<>();
private Map<String, Integer> cnt = new HashMap<>();
public Encrypter(char[] keys, String[] values, String[] dictionary) {
for (int i = 0; i < keys.length; ++i) {
mp.put(keys[i], values[i]);
}
for (String w : dictionary) {
cnt.merge(encrypt(w), 1, Integer::sum);
}
}
public String encrypt(String word1) {
StringBuilder sb = new StringBuilder();
for (char c : word1.toCharArray()) {
if (!mp.containsKey(c)) {
return "";
}
sb.append(mp.get(c));
}
return sb.toString();
}
public int decrypt(String word2) {
return cnt.getOrDefault(word2, 0);
}
}
/**
* Your Encrypter object will be instantiated and called as such:
* Encrypter obj = new Encrypter(keys, values, dictionary);
* String param_1 = obj.encrypt(word1);
* int param_2 = obj.decrypt(word2);
*/class Encrypter {
public:
unordered_map<string, int> cnt;
unordered_map<char, string> mp;
Encrypter(vector<char>& keys, vector<string>& values, vector<string>& dictionary) {
for (int i = 0; i < keys.size(); ++i) {
mp[keys[i]] = values[i];
}
for (auto v : dictionary) {
cnt[encrypt(v)]++;
}
}
string encrypt(string word1) {
string res = "";
for (char c : word1) {
if (!mp.count(c)) {
return "";
}
res += mp[c];
}
return res;
}
int decrypt(string word2) {
return cnt[word2];
}
};
/**
* Your Encrypter object will be instantiated and called as such:
* Encrypter* obj = new Encrypter(keys, values, dictionary);
* string param_1 = obj->encrypt(word1);
* int param_2 = obj->decrypt(word2);
*/type Encrypter struct {
mp map[byte]string
cnt map[string]int
}
func Constructor(keys []byte, values []string, dictionary []string) Encrypter {
mp := map[byte]string{}
cnt := map[string]int{}
for i, k := range keys {
mp[k] = values[i]
}
e := Encrypter{mp, cnt}
for _, v := range dictionary {
e.cnt[e.Encrypt(v)]++
}
return e
}
func (this *Encrypter) Encrypt(word1 string) string {
var ans strings.Builder
for _, c := range word1 {
if v, ok := this.mp[byte(c)]; ok {
ans.WriteString(v)
} else {
return ""
}
}
return ans.String()
}
func (this *Encrypter) Decrypt(word2 string) int {
return this.cnt[word2]
}
/**
* Your Encrypter object will be instantiated and called as such:
* obj := Constructor(keys, values, dictionary);
* param_1 := obj.Encrypt(word1);
* param_2 := obj.Decrypt(word2);
*/class Encrypter {
private mp: Map<string, string> = new Map();
private cnt: Map<string, number> = new Map();
constructor(keys: string[], values: string[], dictionary: string[]) {
for (let i = 0; i < keys.length; i++) {
this.mp.set(keys[i], values[i]);
}
for (const w of dictionary) {
const encrypted = this.encrypt(w);
if (encrypted !== '') {
this.cnt.set(encrypted, (this.cnt.get(encrypted) || 0) + 1);
}
}
}
encrypt(word: string): string {
let res = '';
for (const c of word) {
if (!this.mp.has(c)) {
return '';
}
res += this.mp.get(c);
}
return res;
}
decrypt(word: string): number {
return this.cnt.get(word) || 0;
}
}
/**
* Your Encrypter object will be instantiated and called as such:
* const obj = new Encrypter(keys, values, dictionary);
* const param_1 = obj.encrypt(word1);
* const param_2 = obj.decrypt(word2);
*/