解密消息

难度: Easy

给你字符串 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 <= 2000
key 由小写英文字母及 ' ' 组成
key 包含英文字母表中每个字符（'a' 到 'z'）至少一次
1 <= message.length <= 2000
message 由小写英文字母和 ' ' 组成

Submission

运行时间: 26 ms

内存: 16.0 MB

class Solution:
    def decodeMessage(self, key: str, message: str) -> str:
        cur = "a"
        rules = dict()

        for c in key:
            if c != " " and c not in rules:
                rules[c] = cur
                cur = chr(ord(cur) + 1)

        ans = "".join(rules.get(c, " ") for c in message)
        return ans

Explain

解题思路是首先创建一个映射表(rules)，将加密密钥(key)中每个字母第一次出现的顺序映射到'a'到'z'。首先初始化一个变量(cur)为'a'，遍历key中的每个字符，当遇到非空格字符且该字符不在已有的映射(rules)中时，将该字符与cur关联，并将cur递增到下一个字母。之后，使用这个映射表(rules)来转换消息(message)，如果消息中的字符在映射表中，则替换为对应的值，否则保持为原字符（如空格）。这样就可以得到解密后的消息。

时间复杂度: O(n + m)

空间复杂度: O(1)

class Solution:
    def decodeMessage(self, key: str, message: str) -> str:
        cur = "a"  # 初始化映射的起始字母
        rules = dict()  # 创建映射字典

        for c in key:  # 遍历密钥中的每个字符
            if c != " " and c not in rules:  # 只处理非空格且未映射的字符
                rules[c] = cur  # 建立映射关系
                cur = chr(ord(cur) + 1)  # 移至下一个字母

        ans = "".join(rules.get(c, " ") for c in message)  # 解密消息
        return ans  # 返回解密后的结果

Explore

在构建映射表的过程中，通过检查当前字符是否已存在于映射表中来确保每个字母只被映射一次。如果一个字符不在映射表中，它将被添加到映射表并关联到当前的目标字母；如果已存在，则不进行任何操作，这样就避免了重复映射。

直接跳过已在映射表中的字符是为了保持映射的一致性和避免重复。映射表的目的是将密钥中的每个字母按其首次出现的顺序映射到'a'到'z'。一旦字母被映射，后续相同的字母不应改变其映射关系，以确保解密的一致性。

如果message中的字符是空格或者是没有在密钥`key`中出现过的其他字符，则这些字符不会在映射表中。在这种情况下，这些字符在解密过程中会被保持原样。

是的，映射表构建方法考虑了包括key中包含所有26个字母的情况。初始化时，cur从'a'开始，每次映射一个新字母时递增，直至'z'。一旦映射了26个字母，cur将超出'z'，此时即使key中还有其他字母，也不会再进行新的映射，因为所有可能的26个映射关系已经建立完成。