Question

2325. 解密消息

English Version

题目描述

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

解法

方法一：数组或哈希表

我们可以使用数组或哈希表 $d$ 存储对照表，然后遍历 message 中的每个字符，将其替换为对应的字符即可。

时间复杂度 $O(m + n)$，空间复杂度 $O(C)$。其中 $m$ 和 $n$ 分别为 key 和 message 的长度；而 $C$ 为字符集大小。

class Solution:
  def decodeMessage(self, key: str, message: str) -> str:
    d = {" ": " "}
    i = 0
    for c in key:
      if c not in d:
        d[c] = ascii_lowercase[i]
        i += 1
    return "".join(d[c] for c in message)

class Solution {
  public String decodeMessage(String key, String message) {
    char[] d = new char[128];
    d[' '] = ' ';
    for (int i = 0, j = 0; i < key.length(); ++i) {
      char c = key.charAt(i);
      if (d[c] == 0) {
        d[c] = (char) ('a' + j++);
      }
    }
    char[] ans = message.toCharArray();
    for (int i = 0; i < ans.length; ++i) {
      ans[i] = d[ans[i]];
    }
    return String.valueOf(ans);
  }
}

class Solution {
public:
  string decodeMessage(string key, string message) {
    char d[128]{};
    d[' '] = ' ';
    char i = 'a';
    for (char& c : key) {
      if (!d[c]) {
        d[c] = i++;
      }
    }
    for (char& c : message) {
      c = d[c];
    }
    return message;
  }
};

func decodeMessage(key string, message string) string {
  d := [128]byte{}
  d[' '] = ' '
  for i, j := 0, 0; i < len(key); i++ {
    if d[key[i]] == 0 {
      d[key[i]] = byte('a' + j)
      j++
    }
  }
  ans := []byte(message)
  for i, c := range ans {
    ans[i] = d[c]
  }
  return string(ans)
}

function decodeMessage(key: string, message: string): string {
  const d = new Map<string, string>();
  for (const c of key) {
    if (c === ' ' || d.has(c)) {
      continue;
    }
    d.set(c, String.fromCharCode('a'.charCodeAt(0) + d.size));
  }
  d.set(' ', ' ');
  return [...message].map(v => d.get(v)).join('');
}

use std::collections::HashMap;
impl Solution {
  pub fn decode_message(key: String, message: String) -> String {
    let mut d = HashMap::new();
    for c in key.as_bytes() {
      if *c == b' ' || d.contains_key(c) {
        continue;
      }
      d.insert(c, char::from((97 + d.len()) as u8));
    }
    message
      .as_bytes()
      .iter()
      .map(|c| d.get(c).unwrap_or(&' '))
      .collect()
  }
}

char* decodeMessage(char* key, char* message) {
  int m = strlen(key);
  int n = strlen(message);
  char d[26];
  memset(d, ' ', 26);
  for (int i = 0, j = 0; i < m; i++) {
    if (key[i] == ' ' || d[key[i] - 'a'] != ' ') {
      continue;
    }
    d[key[i] - 'a'] = 'a' + j++;
  }
  char* ans = malloc(n + 1);
  for (int i = 0; i < n; i++) {
    ans[i] = message[i] == ' ' ? ' ' : d[message[i] - 'a'];
  }
  ans[n] = '\0';
  return ans;
}