解密消息

难度:

标签:

题目描述

给你字符串 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 由小写英文字母和 ' ' 组成

代码结果

运行时间: 26 ms, 内存: 16.0 MB

// Java solution using Streams for decrypting the message
// We use a similar approach as the standard Java solution, but leverage Java Streams for concise code.

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class DecryptMessageStream {
    public String decodeMessage(String key, String message) {
        Map<Character, Character> map = new HashMap<>();
        char currentChar = 'a';
        for (char c : key.toCharArray()) {
            if (c != ' ' && !map.containsKey(c)) {
                map.put(c, currentChar);
                currentChar++;
            }
        }
        return message.chars()
                .mapToObj(c -> (char) c)
                .map(c -> c == ' ' ? ' ' : map.get(c))
                .map(String::valueOf)
                .collect(Collectors.joining());
    }
}

// Usage
// DecryptMessageStream decoder = new DecryptMessageStream();
// String result = decoder.decodeMessage("the quick brown fox jumps over the lazy dog", "vkbs bs t suepuv");
// System.out.println(result); // Output: "this is a secret"

解释

方法:

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

时间复杂度:

O(n + m)

空间复杂度:

O(1)

代码细节讲解

🦆

题解中提到的映射表是如何确保每个字母只映射一次，而不重复映射？

▷

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

🦆

在映射表构建过程中，当字符已在映射表中时为什么直接跳过而不进行任何其他操作？

▷

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

🦆

解题思路中提到，对于message中的每个字符，如果不在映射表中则保持原样。在什么情况下，message中的字符会不在映射表中？

▷

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

🦆

题解中使用的映射表构建方法是否考虑了所有的边界情况，比如key中包含所有26个字母的情况？

▷

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

解密消息

题目描述

代码结果

解释

代码细节讲解

相关问题