题目的主要信息：

输入一个单词作为密匙，如果单词中包含有重复的字母，只保留第1个，其余几个丢弃，然后用字母表其他未出现过的字母按顺序接在后面，作为密钥，由A-Z对应这串密钥
输入的密匙不一定是大写字母，但是密钥是大写
在对信息进行加密时，根据密钥与A-Z的一一对应，将每个字母替换为密钥对应的字母(字母字符的大小写状态应该保留)
输入一个密匙和要加密的单词，输出加密后的单词
只会出现大小写字母

方法一：暴力解法

具体做法：

首先我们根据密匙字符串key构建密钥，遍历字符串，将每个字符用toupper()函数转换成大写字母，然后依次加入密钥字符串中，不过在加入之前要先检查密钥字符串中是否出现过这个字符了，若是出现过，我们舍弃。同样的方法，我们遍历大写字母A-Z，也是先检查是否在密钥字符串中出现过了，如果没有，则将其加在后面。由此，构建了密钥。

26个字母的字母顺序正好是0-25对应A-Z，因此我们可以用每个字符减去字符A的ASCⅡ码，得到它将要转换的字符的位置。

那我们遍历要加密的字符串，每个字符减去字符A的ASCⅡ码得到索引，然后根据索引求得它转换后的值。这里为了保持大小写，我们需要分类讨论，因为密钥中只有大写，小写相应字母ASCⅡ码比大写多了32。

#include<iostream>
#include<string>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    string key, words;
    while(cin >> key >> words){
        vector<char> v;
        for(int i = 0; i < key.length(); i++){ //遍历字符串key
            key[i] = toupper(key[i]); //全部转大写
            auto it = find(v.begin(), v.end(), key[i]); //查找是否加入过了
            if(it == v.end()) //非重复加入
                v.push_back(key[i]);
        }
        for(char c = 'A'; c <= 'Z'; c++){ //从A遍历到Z
            auto it = find(v.begin(), v.end(), c); //没有出现过
            if(it == v.end()) 
                v.push_back(c); //才加入
        }
        string output = "";
        for(int i = 0; i < words.length(); i++){ //遍历要加密的字符串
            if(islower(words[i])) //遇到小写字符
                output += v[words[i] - 'a'] + 32; //需要在转出来的大写字母基础上加32
            else
                output += v[words[i] - 'A']; //大写字母直接替换
        }
        cout << output << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (m + n)$ ，其中 $m$ 为字符串key的长度， $n$ 为字符串words的长度，我们需要分别遍历这两个字符串。因为密钥字符串长度不会超过26，因此find函数复杂度为 $O (1)$ ，遍历字符串A-Z也是 $O (1)$
空间复杂度： $O (1)$ ，记录的密钥长度不超过26，属于常数空间

方法二：哈希方式优化

具体做法：

我们可以用哈希表的方式来优化方法一。用一个长度为26的数组表示A-Z是否出现过了，刚好与字母一一对应，这样我们直接查看数组知道之前这个字符是否出现过，不用每次都用find函数来查找，虽然时间都是 $O (1)$ ，但是常数级别上还是有优化。

其他与方法以相同。

alt

#include<iostream>
#include<string>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    string key, words;
    while(cin >> key >> words){
        vector<char> v;
        vector<bool> flag(26, true);
        for(int i = 0; i < key.length(); i++){ //遍历字符串key
            key[i] = toupper(key[i]); //全部转大写
            if(flag[key[i] - 'A']){ //没有在密钥中出现过
                flag[key[i] - 'A'] = false; //设置为该字母出现过了
                v.push_back(key[i]); //加入密钥
            }
        }
        for(char c = 'A'; c <= 'Z'; c++){ //从A遍历到Z
           if(flag[c - 'A']){  //没有在密钥中出现过
               flag[c - 'A'] = false; //设置为该字母出现过了
               v.push_back(c); //加入密钥
           }
        }
        string output = "";
        for(int i = 0; i < words.length(); i++){ //遍历要加密的字符串
            if(islower(words[i])) //遇到小写字符
                output += v[words[i] - 'a'] + 32; //需要在转出来的大写字母基础上加32
            else
                output += v[words[i] - 'A']; //大写字母直接替换
        }
        cout << output << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (m + n)$ ，其中 $m$ 为字符串key的长度， $n$ 为字符串words的长度，我们需要分别遍历这两个字符串
空间复杂度： $O (1)$ ，记录的密钥长度和字母是否出现过的数组不超过26，属于常数空间

题解 | #字符串加密#

题目的主要信息：

方法一：暴力解法

方法二：哈希方式优化