What is the primary approach to solving the 'Encrypt and Decrypt Strings' problem?

The primary approach involves using a hashmap to map characters to encrypted values for encryption and reversing the process for decryption while checking dictionary validity.

How can I efficiently decrypt strings in the 'Encrypt and Decrypt Strings' problem?

Efficient decryption involves splitting the encrypted string into segments of length 2, finding potential matches for each segment, and counting how many resulting strings are valid according to the dictionary.

What is the role of hashmaps in this problem?

Hashmaps are used to quickly map characters to their encrypted values during encryption and to check valid decryption possibilities during decryption.

How do I handle cases where a character isn't found in the 'keys' array?

If a character is not found in the 'keys' array, the encryption process should return an empty string as it cannot be encrypted.

What happens if multiple strings match during decryption?

When multiple possible decrypted strings match, the goal is to count how many of them appear in the 'dictionary'.

#2227

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

加密解密字符串

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

数组哈希表字符串设计字典树

题目描述

给你一个字符数组 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 <= 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 次

lightbulb

解题思路

方法一：哈希表

我们用一个哈希表 $\textit{mp}$ 记录每个字符的加密结果，用另一个哈希表 $\textit{cnt}$ 记录每个加密结果出现的次数。

在构造函数中，我们遍历 $\textit{keys}$ 和 $\textit{values}$ ，将每个字符和其对应的加密结果存入 $\textit{mp}$ 中。然后遍历 $\textit{dictionary}$ ，统计每个加密结果出现的次数。时间复杂度 $(n + m)$ ，其中 $n$ 和 $m$ 分别是 $\textit{keys}$ 和 $\textit{dictionary}$ 的长度。

在加密函数中，我们遍历输入字符串 $\textit{word1}$ 的每个字符，查找其加密结果并拼接起来。如果某个字符没有对应的加密结果，说明无法加密，返回空字符串。时间复杂度 $O(k)$ ，其中 $k$ 是 $\textit{word1}$ 的长度。

在解密函数中，我们直接返回 $\textit{cnt}$ 中 $\textit{word2}$ 对应的次数。时间复杂度 $O(1)$ 。

空间复杂度 $O(n + m)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

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)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Assess the candidate's ability to handle encryption and decryption using hashmaps.
question_mark
Test if the candidate understands the importance of efficient lookups for decryption and encryption.
question_mark
Evaluate how well the candidate can manage complex string manipulations and check for dictionary matches.

warning

常见陷阱

外企场景

error
Failing to handle cases where a character in the string doesn't exist in the 'keys' array, returning an empty string.
error
Inefficient decryption algorithms that fail to quickly find valid strings in the 'dictionary'.
error
Not properly handling the case where a string has multiple possible decrypted matches.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increasing the length of the 'values' array beyond 2 characters, which requires adjustments to the segment length for decryption.
arrow_right_alt
Handling encrypted strings that are extremely large or require optimizations in the lookup process.
arrow_right_alt
Adding multiple dictionaries and handling scenarios with several potential valid decrypted strings for a single encrypted input.

help

常见问题

外企场景

继续练习

#2166 设计位集 #2353 设计食物评分系统 #1948 删除系统中的重复文件夹