LeetCode 题解工作台
解密消息
给你字符串 key 和 message ，分别表示一个加密密钥和一段加密消息。解密 message 的步骤如下： 使用 key 中 26 个英文小写字母第一次出现的顺序作为替换表中的字母 顺序 。 将替换表与普通英文字母表对齐，形成对照表。 按照对照表 替换 message 中的每个字母。 空格 '…
2
题型
7
代码语言
3
相关题
当前训练重点
简单 · 哈希·表·结合·string
答案摘要
我们可以使用数组或哈希表 存储对照表，然后遍历 `message` 中的每个字符，将其替换为对应的字符即可。 时间复杂度 $O(m + n)$，空间复杂度 。其中 和 分别为 `key` 和 `message` 的长度；而 为字符集大小。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·表·结合·string 题型思路
题目描述
给你字符串 key 和 message ，分别表示一个加密密钥和一段加密消息。解密 message 的步骤如下：
- 使用
key中 26 个英文小写字母第一次出现的顺序作为替换表中的字母 顺序 。 - 将替换表与普通英文字母表对齐，形成对照表。
- 按照对照表 替换
message中的每个字母。 - 空格
' '保持不变。
- 例如，
key = "happy boy"（实际的加密密钥会包含字母表中每个字母 至少一次），据此，可以得到部分对照表（'h' -> 'a'、'a' -> 'b'、'p' -> 'c'、'y' -> 'd'、'b' -> 'e'、'o' -> 'f'）。
返回解密后的消息。
示例 1：
输入：key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv" 输出："this is a secret" 解释：对照表如上图所示。 提取 "the quick brown fox jumps over the lazy dog" 中每个字母的首次出现可以得到替换表。
示例 2：
输入：key = "eljuxhpwnyrdgtqkviszcfmabo", message = "zwx hnfx lqantp mnoeius ycgk vcnjrdb" 输出："the five boxing wizards jump quickly" 解释：对照表如上图所示。 提取 "eljuxhpwnyrdgtqkviszcfmabo" 中每个字母的首次出现可以得到替换表。
提示：
26 <= key.length <= 2000key由小写英文字母及' '组成key包含英文字母表中每个字符（'a'到'z'）至少一次1 <= message.length <= 2000message由小写英文字母和' '组成
解题思路
方法一：数组或哈希表
我们可以使用数组或哈希表 存储对照表，然后遍历 message 中的每个字符，将其替换为对应的字符即可。
时间复杂度 ，空间复杂度 。其中 和 分别为 key 和 message 的长度；而 为字符集大小。
class Solution:
def decodeMessage(self, key: str, message: str) -> str:
d = {" ": " "}
i = 0
for c in key:
if c not in d:
d[c] = ascii_lowercase[i]
i += 1
return "".join(d[c] for c in message)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The problem tests familiarity with hash table usage in string processing.
- question_mark
Look for clarity in the candidate’s approach to character mapping.
- question_mark
Watch for edge case handling like spaces in the message.
常见陷阱
外企场景- error
Failing to build the substitution table correctly by not considering the first occurrence of each letter in the key.
- error
Incorrectly handling spaces in the message.
- error
Overcomplicating the mapping process and missing a straightforward approach.
进阶变体
外企场景- arrow_right_alt
Using a shorter key that doesn’t cover all alphabet letters.
- arrow_right_alt
Adding punctuation in the message or key, requiring adjustments.
- arrow_right_alt
Changing the alphabet to lowercase and uppercase combinations.