[LeetCode] 2325. Decode the Message

You are given the strings key and message, which represent a cipher key and a secret message, respectively. The steps to decode message are as follows:

1. Use the first appearance of all 26 lowercase English letters in key as the order of the substitution table.
2. Align the substitution table with the regular English alphabet.
3. Each letter in message is then substituted using the table.
4. Spaces ' ' are transformed to themselves.

• For example, given key = "happy boy" (actual key would have at least one instance of each letter in the alphabet), we have the partial substitution table of ('h' -> 'a', 'a' -> 'b', 'p' -> 'c', 'y' -> 'd', 'b' -> 'e', 'o' -> 'f').

Return the decoded message.

Example 1:

Input: key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv"
Output: "this is a secret"
Explanation: The diagram above shows the substitution table.
It is obtained by taking the first appearance of each letter in "the quick brown fox jumps over the lazy dog".

Example 2:

Input: key = "eljuxhpwnyrdgtqkviszcfmabo", message = "zwx hnfx lqantp mnoeius ycgk vcnjrdb"
Output: "the five boxing wizards jump quickly"
Explanation: The diagram above shows the substitution table.
It is obtained by taking the first appearance of each letter in "eljuxhpwnyrdgtqkviszcfmabo".

Constraints:

• 26 <= key.length <= 2000
• key consists of lowercase English letters and ' '.
• key contains every letter in the English alphabet ('a' to 'z') at least once.
• 1 <= message.length <= 2000
• message consists of lowercase English letters and ' '.

解密消息。

给你字符串 key 和 message ，分别表示一个加密密钥和一段加密消息。解密 message 的步骤如下：

使用 key 中 26 个英文小写字母第一次出现的顺序作为替换表中的字母 顺序 。
将替换表与普通英文字母表对齐，形成对照表。
按照对照表 替换 message 中的每个字母。
空格 ' ' 保持不变。
例如，key = "happy boy"（实际的加密密钥会包含字母表中每个字母 至少一次），据此，可以得到部分对照表（'h' -> 'a'、'a' -> 'b'、'p' -> 'c'、'y' -> 'd'、'b' -> 'e'、'o' -> 'f'）。
返回解密后的消息。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/decode-the-message
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是 hashmap。因为题目只涉及小写字母，所以我们只需要用一个长度为 26 的数组去形成对照表。注意空格需要特别处理，否则在做对照表的时候容易出现越界的报错。

时间O(n)

空间O(1) - 几乎没有使用额外空间，只用了一个长度为 26 的数组

Java实现

 1 class Solution {
 2     public String decodeMessage(String key, String message) {
 3         char[] map = new char[26];
 4         char p = 'a';
 5         for (int i = 0; i < key.length(); i++) {
 6             char c = key.charAt(i);
 7             if (c == ' ') {
 8                 continue;
 9             }
10             if (map[c - 'a'] == 0) {
11                 map[c - 'a'] = p;
12                 p++;
13             }
14         }
15 
16         StringBuilder sb = new StringBuilder();
17         for (int i = 0; i < message.length(); i++) {
18             char c = message.charAt(i);
19             if (c == ' ') {
20                 sb.append(' ');
21             } else {
22                 sb.append(map[c - 'a']);
23             }
24         }
25         return sb.toString();
26     }
27 }

LeetCode 题目总结