描述

有一种技巧可以对数据进行加密，它使用一个单词作为它的密匙。下面是它的工作原理：首先，选择一个单词作为密匙，如TRAILBLAZERS。如果单词中包含有重复的字母，只保留第1个，将所得结果作为新字母表开头，并将新建立的字母表中未出现的字母按照正常字母表顺序加入新字母表。如下所示：

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

T R A I L B Z E S C D F G H J K M N O P Q U V W X Y (实际需建立小写字母的字母表，此字母表仅为方便演示）

上面其他用字母表中剩余的字母填充完整。在对信息进行加密时，信息中的每个字母被固定于顶上那行，并用下面那行的对应字母一一取代原文的字母(字母字符的大小写状态应该保留)。因此，使用这个密匙， Attack AT DAWN (黎明时攻击)就会被加密为Tpptad TP ITVH。

请实现下述接口，通过指定的密匙和明文得到密文。

输入描述：

先输入key和要加密的字符串

输出描述：

返回加密后的字符串

知识点：字符串，

难度：⭐⭐⭐

题解

方法一：模拟字母表

解题思路：

可以通过 List 集合，（大写字母的 ASCII 码 - 32）作为索引，填充为26个字母，要加密的大写字母ASCII码作为索引进行查询加密后的字符

算法流程：

• 维护两个集合，codes 保存建立的字母表，strSet 保存密钥字符，用于去重
• 遍历密钥key，分别填充 codes 和 strSet， 同时在 codes 接着填充字母表，(大写字母的 ASCII 码 - 32) 作为在 codes 的索引
• 遍历要加密的字符串 word，根据字母的ascii码作为数组索引，寻找该位置上的字母，同时注意填充空格 ‘ ’

Java 版本代码如下：

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){
        	String key = scanner.nextLine().toUpperCase();
            String word = scanner.nextLine();
			System.out.println(solution(key, word));
        }
    }

    private static String solution(String key, String word) {
    	List<Character> codes = new ArrayList<>();
    	Set<Character> strSet = new HashSet<>();
    	//  T R A I L B Z E S
    	for(char c : key.toCharArray()) {
    		strSet.add(c);
    		if(!codes.contains(c)) {
    			codes.add(c);
    		}
    	}
    	int index = 0;
    	// codes:  T R A I L B Z E S 后面按顺序补上剩余字母，直到26个字母齐全
    	while(codes.size() < 26) {
    		char c = (char) (index + 'A');
    		if(!strSet.contains(c)) {
    			codes.add(c);
    		}
    		++index;
    	}
    	StringBuilder res = new StringBuilder();
    	for(char c : word.toCharArray()) {
    		if(c == ' ') {
    			res.append(' ');
    			// 根据字母的ascii码作为数组索引，寻找该位置上的字母
    		} else if(c >= 'A' && c <= 'Z') {
    			res.append(codes.get(c - 'A'));
    		} else if(c >= 'a' && c <= 'z') {
    			// 匹配小写字母
    			res.append((char) (codes.get(c - 'a') + 32));
    		}
    	}
        return res.toString();
    }
}

复杂度分析：

时间复杂度：$O(N)O(N)$，需要遍历处理需要加密的字符，N 为需要加密字母数量

空间复杂度：$O(N)O(N)$，StringBuilder 保存加密后的字符串，N 为需要加密字母数量

方法二：有序+自动去重集合

图解：

解题思路：

LinkedHashSet 能实现按添加顺序排序，并自动去重

算法流程：

• 维护一个 LinkedHashSet ， 实现按添加顺序排序，并自动去重
• 遍历密钥字符串 key，填充密钥的大写字母、填充剩余的字母
• 根据字母的ascii码作为数组索引，寻找该位置上的字母

Java 版本代码如下：

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){
        	String key = scanner.nextLine().toUpperCase();
            String word = scanner.nextLine();
			System.out.println(solution(key, word));
        }
    }

    private static String solution(String key, String word) {
    	LinkedHashSet<Character> set = new LinkedHashSet<>();
    	// 填充密钥的大写字母
    	for(char c : key.toCharArray()) {
    		set.add(Character.toUpperCase(c));
    	}
    	// 填充剩余的字母
    	for(char c = 'A'; c <= 'Z'; c++) {
    		// 自动去重
    		set.add(c);
    	}
    	List<Character> codes = new ArrayList<>(set);
    	StringBuilder res = new StringBuilder();
    	for(char c : word.toCharArray()) {
    		if(c == ' ') {
    			res.append(' ');
    			// 根据字母的ascii码作为数组索引，寻找该位置上的字母
    		} else if(c >= 'A' && c <= 'Z') {
    			res.append(codes.get(c - 'A'));
    		} else if(c >= 'a' && c <= 'z') {
    			// 匹配小写字母
    			res.append((char) (codes.get(c - 'a') + 32));
    		}
    	}
        return res.toString();
    }
}

复杂度分析：

时间复杂度：$O(N)O(N)$，需要遍历处理需要加密的字符，N 为需要加密字母数量

空间复杂度：$O(N)O(N)$，StringBuilder 保存加密后的结果，N 为需要加密字母数量