题解 | #playfair#

题意整理

• 给定一种加密算法，通过算法将输入字符串进行加密处理。
• 加密算法需要先通过密钥绘制密码表，然后通过密码表对输入字符串加密。
• 密码表是一个大小为的表格，从前往后一次由密钥中的字母组成，遇到重复的字母，则跳过，如果密钥中的字母用完了，则取标准字母表中的字母。如果遇到字母j，则按照字母i进行处理。
• 得到密码表之后，按输入字符串，每隔两个字母进行一次加密。假设待处理的两个字母是和，如果与相等，则直接写入；如果在同一行，将紧靠、右端字母写入；如果在同一列，将紧靠下方字母写入；如果不同行且不同列，写入矩阵中与同行的另外两角。

方法一（模拟）

1.解题思路

• 首先通过密钥获取密码表。
• 遍历整个str字符串，每次得到当前相邻的两个字符，通过密码表，获取位置信息。根据加密规则进行加密处理。
• 如果字符串长度为偶数，直接加密完成，如果是奇数，需要处理掉最后一个字符（直接写入密文即可）。

动图展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * playfair加密算法
     * @param key string字符串 密钥
     * @param str string字符串 明文
     * @return string字符串
     */
    public String Encode (String key, String str) {
        //获取密码表
        char[][] table=getTable(key);
        int n=str.length();
        //初始化结果
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<=n-2;i+=2){
            //如果是'j'，则替换为'i'
            char p1=str.charAt(i);
            if(p1=='j') p1='i';
            char p2=str.charAt(i+1);
            if(p2=='j') p2='i';
            //获取位置信息
            int[] point1=getPoint(p1,table);
            int[] point2=getPoint(p2,table);
            int row1=point1[0];
            int col1=point1[1];
            int row2=point2[0];
            int col2=point2[1];
            //如果是相同的两个字母，直接写入
            if(p1==p2){
                sb.append(p1).append(p2);
            }
            else{
                //如果是同一行，将紧靠p1p2右端字母写入
                if(row1==row2){
                    char c1=table[row1][(col1+1)%5];
                    char c2=table[row2][(col2+1)%5];
                    sb.append(c1).append(c2);
                }
                //如果是同一列，将紧靠p1p2下方字母写入
                else if(col1==col2){
                    char c1=table[(row1+1)%5][col1];
                    char c2=table[(row2+1)%5][col2];
                    sb.append(c1).append(c2);
                }
                //如果不同行且不同列，写入矩阵中与p1p2同行的另外两角
                else{
                    char c1=table[row1][col2];
                    char c2=table[row2][col1];
                    sb.append(c1).append(c2);
                }
            }
        }

        //如果n是奇数，还需写入最后一个字符
        if(n%2==1){
            sb.append(str.charAt(n-1));
        }
        return sb.toString();
    }

    //绘制密码表
    private char[][] getTable(String key){
        char[][] arr=new char[5][5];
        boolean[] f=new boolean[26];
        key=key+"abcdefghiklmnopqrstuvwxyz";
        int index=0;
        for(int i=0;i<5;i++){
            for(int j=0;j<5;){
                char c=key.charAt(index++);
                if(c=='j'){
                    c='i';
                }
                //只有字母c未被标记，才写入密码表
                if(!f[c-'a']){
                    f[c-'a']=true;
                    arr[i][j++]=c;
                }
            }
        }
        return arr;
    }

    //从密码表获取当前字符的位置信息
    private int[] getPoint(char c,char[][] table){
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                if(table[i][j]==c){
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }
}

3.复杂度分析

• 时间复杂度：绘制密码表和通过密码表获取字符位置都只需要常数次操作，另外需要遍历整个str字符串，所以时间复杂度为。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为。

方法二（模拟+哈希表）

1.解题思路

思路与方法一大致相同，只是利用哈希表来获取字符在密码表中的位置，一定程度上减少了操作次数。原来最多需要循环次才能找到位置，现在只需获取字符键对应的值，即可直接找到位置。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * playfair加密算法
     * @param key string字符串 密钥
     * @param str string字符串 明文
     * @return string字符串
     */
    //初始化哈希表
    Map<Character,int[]> map=new HashMap<>();

    public String Encode (String key, String str) {
        //获取密码表
        char[][] table=getTable(key);
        int n=str.length();
        //初始化结果
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<=n-2;i+=2){
            //如果是'j'，则替换为'i'
            char p1=str.charAt(i);
            if(p1=='j') p1='i';
            char p2=str.charAt(i+1);
            if(p2=='j') p2='i';
            //根据键值获取位置信息
            int[] point1=map.get(p1);
            int[] point2=map.get(p2);
            int row1=point1[0];
            int col1=point1[1];
            int row2=point2[0];
            int col2=point2[1];
            //如果是相同的两个字母，直接写入
            if(p1==p2){
                sb.append(p1).append(p2);
            }
            else{
                //如果是同一行，将紧靠p1p2右端字母写入
                if(row1==row2){
                    char c1=table[row1][(col1+1)%5];
                    char c2=table[row2][(col2+1)%5];
                    sb.append(c1).append(c2);
                }
                //如果是同一列，将紧靠p1p2下方字母写入
                else if(col1==col2){
                    char c1=table[(row1+1)%5][col1];
                    char c2=table[(row2+1)%5][col2];
                    sb.append(c1).append(c2);
                }
                //如果不同行且不同列，写入矩阵中与p1p2同行的另外两角
                else{
                    char c1=table[row1][col2];
                    char c2=table[row2][col1];
                    sb.append(c1).append(c2);
                }
            }
        }

        //如果n是奇数，还需写入最后一个字符
        if(n%2==1){
            sb.append(str.charAt(n-1));
        }
        return sb.toString();
    }

    //绘制密码表
    private char[][] getTable(String key){
        char[][] arr=new char[5][5];
        boolean[] f=new boolean[26];
        key=key+"abcdefghiklmnopqrstuvwxyz";
        int index=0;
        for(int i=0;i<5;i++){
            for(int j=0;j<5;){
                char c=key.charAt(index++);
                if(c=='j'){
                    c='i';
                }
                //只有字母c未被标记，才写入密码表
                if(!f[c-'a']){
                    f[c-'a']=true;
                    //将位置信息放入哈希表
                    map.put(c,new int[]{i,j});
                    //给密码表赋值
                    arr[i][j++]=c;
                }
            }
        }
        return arr;
    }

    //从密码表获取当前字符的位置信息
    private int[] getPoint(char c,char[][] table){
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                if(table[i][j]==c){
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }
}

3.复杂度分析

• 时间复杂度：绘制密码表和通过哈希表获取字符位置都只需要常数次操作，另外需要遍历整个str字符串，所以时间复杂度为。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为。