跳至主要內容

2325. 解密消息

2325. 解密消息

🟢   🔖  哈希表 字符串  🔗 力扣open in new window LeetCodeopen in new window

题目

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 f o x j u mps o v er the lazy d o g ".

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 的步骤如下：

  1. 使用 key 中 26 个英文小写字母第一次出现的顺序作为替换表中的字母 顺序 。
  2. 将替换表与普通英文字母表对齐，形成对照表。
  3. 按照对照表 替换 message 中的每个字母。
  4. 空格 ' ' 保持不变。
  • 例如，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 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 由小写英文字母和 ' ' 组成

解题思路

  1. 构建字母映射表：

    • 使用一个 Set 来存储已经处理过的字母，保证每个字母只出现一次。
    • 使用一个 substitution 对象来存储字母的映射关系。每遇到一个新字母时，将它映射为字母表中的一个字母，从 a 开始。
    • 一旦映射表中有了 26 个字母，提前结束遍历。

  2. 解码消息：

    • 对消息中的每个字符：
      • 如果是空格，直接将空格加入结果。
      • 如果是字母，根据映射表找到对应的解码字母并加入结果。

  3. 返回解码后的字符串：最后将结果数组连接成一个字符串并返回。

复杂度分析

  • 时间复杂度：O(m)

    • 构建映射表的时间复杂度为 O(k)，其中 k 是 key 的长度。由于最多只需要遍历 26 个字符，实际复杂度为 O(26)，即常数时间。
    • 解码消息的时间复杂度为 O(m)，其中 m 是 message 的长度。

  • 空间复杂度：O(m)

    • 使用了一个 substitution 对象和一个 Set，它们的空间复杂度为 O(1)（固定的字母数量）。
    • 结果数组 res 的空间复杂度为 O(m)，其中 m 是消息的长度。

代码

/**
 * @param {string} key
 * @param {string} message
 * @return {string}
 */
var decodeMessage = function (key, message) {
	let substitution = {};
	let set = new Set();
	let i = 97; // 'a' 的 ASCII 码
	for (let char of key) {
		if (char !== ' ' && !set.has(char)) {
			set.add(char);
			substitution[char] = String.fromCharCode(i++);
		}
		if (set.size === 26) break;
	}

	// 解码消息
	let res = [];
	for (let char of message) {
		if (char === ' ') {
			res.push(' ');
		} else {
			res.push(substitution[char]);
		}
	}

	return res.join('');
};
Copyright © 2024 2xiao