Leetcode 2325.解密消息

给你字符串 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.给我字符串key和message

2.key 加密密匙 message 加密信息

3.解密message步骤

1.将key中的26个英文小写字母

二、步骤

该如何设计步骤呢？

第一步 肯定是接收两个字符串

第二步 建立一个字母表字符串

第三步 对传进来的密文字符串进行遍历并与key和标准字母表进行比较

第四步 进行字符数组的替换遍历完为止

第五步 然后输出字符串

三、分析

问题出现：

问题1.如何进行比较替换呢？

其实不难发现每一个对应的字符串下标都相等我们只需要现在key中找到密文的字母然后再字母表字符串中找到对应的字符然后替换即可。

问题2.字符串之间该如何替换呢？

很简单用C++或C里的函数库即可，JAVA还没学完。

我的答案：

为了实现这个解密算法，我们可以按照以下步骤来解决这个问题。

### 思考过程与分析
1. **创建映射表：**
   遍历密钥字符串（key），对于每个字符，如果它是第一次出现，则将其添加到映射表中。映射表可以是一个数组，其中索引是密文字符，值是对应的明文字符。
   
2. **解密消息：**
   遍历消息字符串（message），对于每个字符，查找映射表并将其替换为相应的字符。空格字符保持不变。

3. **边界与异常处理：**
   一些细节需要注意，例如处理key中的空格字符以及确保映射表是完整的（包含所有26个字母）。

### C语言实现

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

void decrypt(char* key, char* message, char* output) {
    bool used[26] = {0}; // 记录哪些字符已经出现过
    char map[26]; // 映射表
    int idx = 0; // 映射表索引
    
    // 创建映射表
    for(int i = 0; key[i] != '\0'; i++) {
        if(key[i] == ' ') continue; // 跳过空格
        if(!used[key[i] - 'a']) {
            map[idx++] = key[i];
            used[key[i] - 'a'] = true;
        }
    }
    
    // 解密消息
    for(int i = 0; message[i] != '\0'; i++) {
        if(message[i] == ' ') {
            output[i] = ' ';
        } else {
            output[i] = 'a' + (message[i] - 'a' + 26 - idx) % 26;
        }
    }
    output[strlen(message)] = '\0'; // 添加字符串结束标记
}

int main() {
    char key[] = "the quick brown fox jumps over the lazy dog";
    char message[] = "vkbs bs t suepuv";
    char output[2000];
    
    decrypt(key, message, output);
    
    printf("%s\n", output); // 输出：this is a secret
    
    return 0;
}

### C++实现

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

string decrypt(const string& key, const string& message) {
    unordered_set<char> used;
    vector<char> map;
    
    // 创建映射表
    for(char c: key) {
        if(c == ' ') continue;
        if(used.find(c) == used.end()) {
            map.push_back(c);
            used.insert(c);
        }
    }
    
    // 解密消息
    string output(message.length(), ' ');
    for(size_t i = 0; i < message.length(); i++) {
        if(message[i] == ' ') continue;
        output[i] = 'a' + (message[i] - 'a' + 26 - map.size()) % 26;
    }
    return output;
}

int main() {
    string key = "the quick brown fox jumps over the lazy dog";
    string message = "vkbs bs t suepuv";
    
    cout << decrypt(key, message) << endl; // 输出：this is a secret
    
    return 0;
}

### Java实现

import java.util.HashSet;

public class DecryptMessage {
    public static String decrypt(String key, String message) {
        HashSet<Character> used = new HashSet<>();
        StringBuilder map = new StringBuilder();
        
        // 创建映射表
        for(char c: key.toCharArray()) {
            if(c == ' ') continue;
            if(!used.contains(c)) {
                map.append(c);
                used.add(c);
            }
        }
        
        // 解密消息
        StringBuilder output = new StringBuilder(message.length());
        for(char c: message.toCharArray()) {
            if(c == ' ') {
                output.append(' ');
                continue;
            }
            output.append((char) ('a' + (c - 'a' + 26 - map.length()) % 26));
        }
        return output.toString();
    }

    public static void main(String[] args) {
        String key = "the quick brown fox jumps over the lazy dog";
        String message = "vkbs bs t suepuv";
        
        System.out.println(decrypt(key, message)); // 输出：this is a secret
    }
}

### 可能遇到的问题
- 如果key中不包含所有26个字母，映射表将无法构建。
- 确保不要修改原始消息字符串，而是创建一个新的字符串来存储解密后的消息。
- 需要跳过key中的空格字符，并且确保输出字符串中的空格与输入消息字符串中的空格对应。
- 需要处理字符的循环映射，例如，z映射到a。

英雄师傅的答案：

char* decodeMessage(char* key, char* message) {
	char hash[256];
	int i;
	char alph = 'a';
	memset(hash, 0, sizeof(hash));
	for (i = 0; key[i]; ++i) {
		if (key[i] != ' ') {
			if (!hash[key[i]]) {
				hash[key[i]] = alph++;
			}
		}
	}
	for (i = 0; , message[i]; ++i) {
		if (message[i] != ' ') {
			message[i] = hash[message[i]];
		}
	}
	return message;
}

英雄师傅的解决方案很聪明，代码也很简洁。下面是代码的分析以及它是如何工作的。

分析过程

1. 建立哈希表： 这个解决方案中使用了一个hash数组，用于存储密钥（key）中每个字符的映射。hash数组的索引是字符的ASCII值，而值是映射的字符。例如，如果hash['h']是 'a'，那么在消息（message）中的 'h' 将被替换为 'a'。

2. 初始化映射： 初始化变量alph为 'a'，以便将密钥中的每个唯一字符映射到英文字母表中的字符。对于密钥中的每个字符，如果它不是空格并且尚未映射（即 hash[key[i]] 为0），则映射它并递增 alph。

3. 解密消息： 遍历消息中的每个字符。如果字符不是空格，则将其替换为hash中的映射字符。

4. 返回消息： 函数最终返回修改后的消息字符串。

Leetcode官方题解：

方法一：模拟
思路与算法

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

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

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

源代码：

C++：

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;
    }
};

JAVA：

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();
    }
}

总结：

一、学到了什么

这道题目提供了一次优秀的学习机会，涉及到几个关键的编程和计算机科学概念：

1. 哈希表/数组映射

哈希表是一种数据结构，用于存储键值对。在这个解决方案中，使用了一个字符数组作为一个简单的哈希表，其中索引是字符的ASCII值，而值是该字符的映射。学会如何使用哈希表是解决类似问题的关键。

2. 字符串操作

解决这个问题需要对字符串进行遍历和修改。需要理解如何使用字符串和数组，如何遍历它们，如何修改字符串中的单个字符，这是编程中常见的需求。

3. 条件判断

解决方案中使用了条件判断来检查字符是否为空格，以及字符是否已经被映射。掌握条件判断语句对于实现更复杂的逻辑至关重要。

4. 循环

通过循环来遍历字符串是一个基本的编程概念。在这个问题中，我们看到了如何使用for循环来遍历字符串，并基于某个条件来修改它。

5. 内存管理

通过memset函数初始化数组，是C语言中内存管理的一个例子。理解如何初始化和管理内存是使用低级语言（如C）编程的一个重要方面。

6. 解密和编码

这个问题还涉及到简单的解密概念。虽然这个问题的加密/解密过程比现实中的要简单得多，但它提供了对于如何使用映射和转换来解密文本的基础理解。

7. 优化

这个方案中直接修改了输入的消息字符串，避免了使用额外空间。这是一个优化，它减少了程序的空间复杂度。在实际问题中，考虑如何优化代码以减少空间和时间复杂度是非常重要的。

8. 测试与调试

给定代码中的小错误（循环中的逗号），表明测试和调试是编写代码的重要部分。即使代码看起来很简单，也可能包含错误或bug，因此测试代码以确保其正确性是必要的。

总结

这道题目是学习和练习基础编程概念、数据结构操作、内存管理和简单加密解密概念的好机会。同时，它也强调了测试、调试和优化的重要性。

二、思想思维和方法：

通过这道题目和题解，我们可以学到以下几点思想、方法和思维：

### 1. **问题分解**
学习将问题分解成较小、更易管理的部分。例如，此问题可以分解为两个主要部分：构建映射表和解密消息。将问题分解成小部分有助于更清晰地理解问题并逐步解决它。

### 2. **简化问题**
在构建解决方案时，寻找将问题简化的方法。在这个例子中，使用字符数组作为简单的哈希表可以简化解决方案，而不需要复杂的数据结构。

### 3. **避免不必要的复杂性**
优先寻求简单、直接的解决方案。在这个例子中，我们看到如何通过直接修改输入字符串来避免额外的空间复杂性。

### 4. **自顶向下的思维**
首先构思整体解决方案的框架，然后详细处理实现的具体细节。例如，先确定需要构建映射表，然后实现具体的映射表构建过程。

### 5. **迭代改进**
开始于基础解决方案，并逐步优化。例如，首先实现一个基本的解密过程，然后考虑如何减少空间和时间复杂性。

### 6. **注意边界条件**
仔细考虑并处理输入的各种可能性，包括空字符串、特殊字符等。这有助于编写健壮的代码，能够处理各种情况。

### 7. **测试驱动的开发**
从题解中的错误，我们可以学到编写测试用例并进行严格测试的重要性。这有助于早期发现和修复错误，确保代码的正确性。

### 8. **数据结构和算法知识**
了解并熟悉各种数据结构和算法是解决此类问题的基础。例如，了解哈希表、字符串操作和基础算法有助于更有效地解决问题。

### 9. **逐步推导**
对于映射表的构建和解密过程，应该进行逐步推导，一步一步验证每个过程的正确性，这是一种解决问题和调试的有效方法。

### 10. **细心与耐心**
编程时要保持细心，对待每一处细节都不能马虎，同时在调试过程中要保持耐心，逐一排查可能的错误来源。

总之，这道题目提供了对基本编程原则、问题解决方法和计算机科学基础知识的实践机会，通过实际操作，可以加深对这些概念和技巧的理解。