2227-加密解密字符串

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

给你一个字符数组 keys ，由若干 互不相同 的字符组成。还有一个字符串数组 values ，内含若干长度为 2
的字符串。另给你一个字符串数组 dictionary ，包含解密后所有允许的原字符串。请你设计并实现一个支持加密及解密下标从 0
开始字符串的数据结构。

字符串 加密 按下述步骤进行：

  1. 对字符串中的每个字符 c ，先从 keys 中找出满足 keys[i] == c 的下标 i 。
  2. 在字符串中，用 values[i] 替换字符 c 。

字符串 解密 按下述步骤进行：

  1. 将字符串每相邻 2 个字符划分为一个子字符串，对于每个子字符串 s ，找出满足 values[i] == s 的一个下标 i 。如果存在多个有效的 i ，从中选择 任意 一个。这意味着一个字符串解密可能得到多个解密字符串。
  2. 在字符串中，用 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 <= 26
  • values[i].length == 2
  • 1 <= dictionary.length <= 100
  • 1 <= dictionary[i].length <= 100
  • 所有 keys[i] 和 dictionary[i] 互不相同
  • 1 <= word1.length <= 2000
  • 1 <= word2.length <= 200
  • 所有 word1[i] 都出现在 keys 中
  • word2.length 是偶数
  • keys、values[i]、dictionary[i]、word1 和 word2 只含小写英文字母
  • 至多调用 encrypt 和 decrypt 总计 200 次

方法一：直接加密 + 预处理解密

思路与算法

我们首先可以使用 enc 哈希映射存储单个字母的加密关系，即对于 enc 中的每个键值对，键表示单个字母，值表示该字母加密得到的长度为 2 的字符串。这样一来，对于 encrypt(word) 操作，我们只需要遍历字符串 word，对每个字母分别根据哈希映射进行加密，再合并结果得到最终的字符串即可。

而对于 decrypt(word) 操作，如果我们直接按照题目中的要求进行分组、解密、判断是否在字典中，那么必然会使用深度优先搜索或者更高级的数据结构（例如字典树）。一种更简单的方法是「逆向思考」：我们直接把字典中的所有单词进行加密，如果该单词可以被加密，那么我们就将加密的结果存储在另一个哈希映射 dec_count 中，键表示加密的结果，值表示该结果出现的次数（因为多个单词可以被加密成相同的结果）。这样一来，我们只需要返回 word 作为键在哈希映射中对应的值即可。

代码

[sol1-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
29
30
31
32
33
34
35
36
37
class Encrypter {
private:
    unordered_map<char, string> enc;
    unordered_map<string, int> dec_count;
    
public:
    Encrypter(vector<char>& keys, vector<string>& values, vector<string>& dictionary) {
        int n = keys.size();
        for (int i = 0; i < n; ++i) {
            enc[keys[i]] = values[i];
        }
        
        for (const string& word: dictionary) {
            string result = encrypt(word);
            if (result != "") {
                ++dec_count[result];
            }
        }
    }
    
    string encrypt(string word1) {
        string result;
        for (char ch: word1) {
            if (enc.count(ch)) {
                result += enc[ch];
            }
            else {
                return "";
            }
        }
        return result;
    }
    
    int decrypt(string word2) {
        return dec_count.count(word2) ? dec_count[word2] : 0;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Encrypter:

    def __init__(self, keys: List[str], values: List[str], dictionary: List[str]):
        self.enc = {key: value for key, value in zip(keys, values)}
        self.dec_count = Counter()
        for word in dictionary:
            if (result := self.encrypt(word)) != "":
                self.dec_count[result] += 1 

    def encrypt(self, word1: str) -> str:
        result = list()
        for ch in word1:
            if ch in self.enc:
                result.append(self.enc[ch])
            else:
                return ""
        return "".join(result)

    def decrypt(self, word2: str) -> int:
        return self.dec_count[word2] if word2 in self.dec_count else 0

复杂度分析

  • 时间复杂度：

    • 初始化的时间复杂度为 O(k + d \times l_d)，其中 k 分别是数组 keys 和 values 的长度，d 是数组 dictionary 的长度，l_d 是数组 dictionary 中单词的平均长度；

    • encrypt(word) 的时间复杂度为 O(|\textit{word}|)；

    • decrypt(word) 的时间复杂度为 O(|\textit{word}|)。

  • 空间复杂度：O(k + d \times l_d)，即为两个哈希映射需要使用的空间。

 Comments
On this page
2227-加密解密字符串