2325-解密消息

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

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

  1. 使用 key 中 26 个英文小写字母第一次出现的顺序作为替换表中的字母 顺序 。
  2. 将替换表与普通英文字母表对齐，形成对照表。
  3. 按照对照表 替换 message 中的每个字母。
  4. 空格 ' ' 保持不变。
  • 例如，key = " _ **hap**_ p _ **y**_ _**bo**_ y"（实际的加密密钥会包含字母表中每个字母 至少一次 ），据此，可以得到部分对照表（'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**_ _**f**_ o _ **x**_ _**j**_ u _ **mps**_ o _ **v**_ er the _**lazy**_ _**d**_ o _ **g**_ " 中每个字母的首次出现可以得到替换表。

示例 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 由小写英文字母和 ' ' 组成

方法一：模拟

思路与算法

我们根据题目的要求进行模拟即可。

具体地，我们使用一个哈希表存储替换表，随后对字符串 key 进行遍历。当我们遍历到一个不为空格且未在哈希表中出现的字母时，就将当前字母和 cur 作为键值对加入哈希表中。这里的 cur 即为替换之后的字母，它的初始值为字母 `a’，当哈希表中每添加一个键值对后，cur 就会变为下一个字母。

在这之后，我们再对字符串 message 进行遍历，就可以得到答案。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string decodeMessage(string key, string message) {
        char cur = 'a';
        unordered_map<char, char> rules;

        for (char c: key) {
            if (c != ' ' && !rules.count(c)) {
                rules[c] = cur;
                ++cur;
            }
        }

        for (char& c: message) {
            if (c != ' ') {
                c = rules[c];
            }
        }

        return message;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public String decodeMessage(String key, String message) {
        char cur = 'a';
        Map<Character, Character> rules = new HashMap<Character, Character>();

        for (int i = 0; i < key.length(); ++i) {
            char c = key.charAt(i);
            if (c != ' ' && !rules.containsKey(c)) {
                rules.put(c, cur);
                ++cur;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < message.length(); ++i) {
            char c = message.charAt(i);
            if (c != ' ') {
                c = rules.get(c);
            }
            sb.append(c);
        }

        return sb.toString();
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public string DecodeMessage(string key, string message) {
        char cur = 'a';
        IDictionary<char, char> rules = new Dictionary<char, char>();

        foreach (char c in key) {
            if (c != ' ' && !rules.ContainsKey(c)) {
                rules.Add(c, cur);
                ++cur;
            }
        }

        StringBuilder sb = new StringBuilder();
        foreach (char c in message) {
            if (c != ' ') {
                sb.Append(rules[c]);
            } else {
                sb.Append(c);
            }
        }

        return sb.ToString();
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
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
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
char * decodeMessage(char * key, char * message){
    char cur = 'a';
    char rules[26];
    memset(rules, 0, sizeof(rules));

    for (int i = 0; key[i] != '\0'; i++) {
        char c = key[i];
        if (c != ' ' && !rules[c - 'a']) {
            rules[c - 'a'] = cur;
            ++cur;
        }
    }

    for (int i = 0; message[i] != '\0'; i++) {
        char c = message[i];
        if (c != ' ') {
            message[i] = rules[c - 'a'];
        }
    }

    return message;
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func decodeMessage(key string, message string) string {
    cur := byte('a')
    rules := map[rune]byte{}

    for _, c := range key {
        if c != ' ' && rules[c] == 0 {
            rules[c] = cur
            cur++
        }
    }

    m := []byte(message)
    for i, c := range message {
        if c != ' ' {
            m[i] = rules[c]
        }
    }

    return string(m)
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var decodeMessage = function(key, message) {
    let cur = 'a';
    const rules = new Map();

    for (let i = 0; i < key.length; ++i) {
        const c = key[i];
        if (c !== ' ' && !rules.has(c)) {
            rules.set(c, cur);
            cur = String.fromCharCode(cur.charCodeAt() + 1);
        }
    }

    let ret = '';
    for (let i = 0; i < message.length; ++i) {
        let c = message[i];
        if (c !== ' ') {
            c = rules.get(c);
        }
        ret += c;
    }

    return ret;
};

复杂度分析

  • 时间复杂度：O(m+n)，其中 m 和 n 分别是字符串 key 和 message 的长度。

  • 空间复杂度：O(|\Sigma|) 或者 O(n + |\Sigma|)，其中 \Sigma 是字符集，在本题中 |\Sigma|=26。哈希表需要使用 O(|\Sigma|) 的空间。此外，如果我们使用的语言不能对字符串进行修改，就需要额外 O(n) 的空间存储答案的临时表示；否则可以在给定的字符串 message 上进行修改。

 Comments
On this page
2325-解密消息