Easy

题目描述

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

解题思路

解题思路

这道题的核心是构建一个字符映射表，将密钥中的字符映射到标准字母表。

算法步骤：

  1. 构建映射表：遍历密钥字符串，记录每个字母第一次出现的位置，按顺序映射到 ‘a’ 到 ‘z’
  2. 解码消息：使用构建的映射表对消息进行字符替换

具体实现：

  • 使用哈希表记录密钥字符到标准字母的映射关系
  • 遍历密钥时，只记录每个字符的第一次出现，忽略空格和重复字符
  • 使用一个计数器来追踪当前应该映射到的标准字母（从 ‘a’ 开始）
  • 最后遍历消息字符串，根据映射表进行字符替换，空格保持不变

时间复杂度： O(n + m)，其中 n 是密钥长度，m 是消息长度 空间复杂度： O(1)，映射表最多存储 26 个字符映射

代码实现

class Solution {
public:
    string decodeMessage(string key, string message) {
        unordered_map<char, char> mapping;
        char current = 'a';
        
        // 构建映射表
        for (char c : key) {
            if (c != ' ' && mapping.find(c) == mapping.end()) {
                mapping[c] = current++;
            }
        }
        
        // 解码消息
        string result;
        for (char c : message) {
            if (c == ' ') {
                result += ' ';
            } else {
                result += mapping[c];
            }
        }
        
        return result;
    }
};

class Solution:
    def decodeMessage(self, key: str, message: str) -> str:
        mapping = {}
        current = ord('a')
        
        # 构建映射表
        for c in key:
            if c != ' ' and c not in mapping:
                mapping[c] = chr(current)
                current += 1
        
        # 解码消息
        result = []
        for c in message:
            if c == ' ':
                result.append(' ')
            else:
                result.append(mapping[c])
        
        return ''.join(result)

public class Solution {
    public string DecodeMessage(string key, string message) {
        Dictionary<char, char> mapping = new Dictionary<char, char>();
        char current = 'a';
        
        // 构建映射表
        foreach (char c in key) {
            if (c != ' ' && !mapping.ContainsKey(c)) {
                mapping[c] = current++;
            }
        }
        
        // 解码消息
        StringBuilder result = new StringBuilder();
        foreach (char c in message) {
            if (c == ' ') {
                result.Append(' ');
            } else {
                result.Append(mapping[c]);
            }
        }
        
        return result.ToString();
    }
}

/**
 * @param {string} key
 * @param {string} message
 * @return {string}
 */
var decodeMessage = function(key, message) {
    const map = new Map();
    let alphabet = 'abcdefghijklmnopqrstuvwxyz';
    let alphabetIndex = 0;
    
    for (let char of key) {
        if (char !== ' ' && !map.has(char)) {
            map.set(char, alphabet[alphabetIndex]);
            alphabetIndex++;
        }
    }
    
    let result = '';
    for (let char of message) {
        if (char === ' ') {
            result += ' ';
        } else {
            result += map.get(char);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m)n 为 key 长度，m 为 message 长度，需要遍历两个字符串各一次
空间复杂度O(1)映射表最多存储 26 个字符映射，为常数空间