加密解密字符串

难度: Hard

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

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

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

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

将字符串每相邻 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 <= 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 次

Submission

运行时间: 138 ms

内存: 21.3 MB

class Encrypter:
    def __init__(self, keys: List[str], values: List[str], dictionary: List[str]):
        self.dic = {}
        for a, b in zip(keys, values):
            self.dic[a] = b
        
        self.d = defaultdict(int)
        for word in dictionary:
            if all(ch in self.dic for ch in word):
                encode = "".join(self.dic[key] for key in word)
                self.d[encode] += 1

    def encrypt(self, word1: str) -> str:
        return "".join(self.dic[key] for key in word1)

    def decrypt(self, word2: str) -> int:
        return self.d[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)

Explain

这个解题思路包括了加密和解密两部分的实现。加密部分将每个字符映射到对应的字符串，并将这些字符串连接起来形成加密后的字符串。解密部分则是通过预计算字典中每个单词的加密结果，并存储这些结果出现的次数。解密时直接查找给定加密字符串在预计算结果中的次数。这样可以快速解密，而不需要每次都动态计算。

时间复杂度: 构造函数：O(n*m), encrypt函数：O(p), decrypt函数：O(1)

空间复杂度: O(k + n)

class Encrypter:
    def __init__(self, keys: List[str], values: List[str], dictionary: List[str]):
        # 创建加密映射
        self.dic = {}
        for a, b in zip(keys, values):
            self.dic[a] = b
        
        # 预计算字典中每个单词的加密结果并计数
        self.d = defaultdict(int)
        for word in dictionary:
            if all(ch in self.dic for ch in word):
                encode = \"\".join(self.dic[key] for key in word)
                self.d[encode] += 1
    
    def encrypt(self, word1: str) -> str:
        # 加密输入字符串
        return \"\".join(self.dic[key] for key in word1)
    
    def decrypt(self, word2: str) -> int:
        # 解密字符串并返回可能的原字符串数目
        return self.d[word2]

Explore

预先计算字典中每个单词的加密结果并进行计数的做法主要是为了提高解密过程的效率。这种方式允许解密函数通过简单的哈希表查找，即可迅速得到一个加密字符串对应的所有可能原始单词的数量，而不需要重新对每个字典词条进行加密比较。这减少了重复的计算工作，特别是在字典较大或解密操作频繁的情况下，可以显著提高解密速度。

如果多个原始单词加密后得到相同的字符串，解密函数会返回这些单词的总数。在Encrypter类的构造过程中，每个加密字符串对应的计数值会累加所有映射到该字符串的原始单词的数量。因此，解密时，返回的是加密字符串在预计算哈希表中的计数，这个计数反映了能够产生相同加密字符串的所有不同原始单词的总数。

如果解密时给定的加密字符串在哈希表中不存在，这意味着没有任何字典中的单词在加密后可以生成这个字符串。在这种情况下，解密函数应返回0，表示不存在任何有效的原始单词映射到提供的加密字符串。

在创建加密映射时，如果values数组中存在重复的字符串，这可能会导致不同的keys映射到同一个value，从而在加密过程中导致信息的丢失或混淆。为确保加密的一致性和解密的正确性，最好避免这种设计。如果无法避免，应确保在解密时能够处理同一加密结果对应多个可能原始单词的情况。这通常意味着解密结果可能会返回多个潜在的匹配项的数量，而不是确切的单个原始单词。