题目的主要信息：

• 用playfair加密信息:加密过程中的$jj$都由$ii$来代替

• playfair加密算法首先需要绘制密码表，密码表是一个$5\ast 55*5$的矩阵，开始由密钥(key)按顺序排列，其余按照未出现的字母顺序

• 若密钥中含有重复字母需要将重复字母去掉，若有$jj$用$ii$来代替

• 加密明文需要符合以下规则：

  1. 将明文中每两个字母组成一对，若成对后是两个相同字母或留下一个字母无法成对，则不进行变化直接放入密文中

  2. 明文对p1p2在同一行，对应密文对c1c2分别为紧靠p1p2右端的字母，最后一列右端对应第一列

  3. 明文对p1p2在同一列，对应密文对c1c2分别为紧靠p1p2下方的字母，最后一行下方对应第一行

  4. 明文对p1p2不在同一行且不在同一列，对应密文对c1c2分别为p1p2确定的矩形中的同行另外两角

• 只会出现小写字母

方法一：暴力模拟

具体做法：

首先我们画密码表，设置两个指针并遍历$5\ast 55*5$的二维数组，指针p指向字符串key的下标，指针q指向26个小写字母，先用p指针遍历key，再用q指针遍历字母。并用一个长度为26的数组表示字母是否出现过，因为表中每个字母只出现了一次，当然j一开始就置为1，因为没有j。遍历的时候，遇到第一次出现的字母才添加到密码表中，如果遍历的时候出现了重复的字母，需要回溯矩阵的指针，防止出现空位。也要注意，一旦出现j要换成i。

构建好密码表之后，我们两个字符两个字符地遍历所给的字符串，注意所有的j要变成i以后再处理。如果两个字符相同则不变动，当然奇数长度字符串最后一位我们跳过去了，也是不变动。然后每次检查两个字符在密码表中的位置（这里可以直接暴力搜索密码表找到相同的字符的位置即可），然后比较两个字符的行列坐标，按照上述要求进行变换取值。因为行或者列的末尾要回到第一行或者列，我们采用取模的方式来进行。

class Solution {
public:
    pair<int, int> getindex(char c, vector<vector<char>>& table){ //遍历密码表，找到字符c的位置
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                if(table[i][j] == c)
                    return make_pair(i, j);
            }
        }
        return make_pair(0, 0); //一定能找到，因此随便返回
    }
    string Encode(string key, string str) {
        vector<bool> vis(26, false);
        vector<vector<char> > table(5, vector<char>(5));
        int p = 0; //字符串key的指针
        int q = 0; //字母表abcd……的指针
        vis['j' - 'a'] = true; //字母表中没有j
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                if(p < key.length()){
                    if(key[p] == 'j') //j换成i
                        key[p] = 'i';
                    if(!vis[key[p] - 'a']){ //没有出现过的字母才加入
                        vis[key[p] - 'a'] = true;
                        table[i][j] = key[p];
                    }else
                        j--; //字符串指针后移，矩阵指针不动
                    p++;
                }else{
                    if(!vis[q]){ //没有出现过的字母才加入
                        table[i][j] = q + 'a';
                    }else
                        j--; //字符串指针后移，矩阵指针不动
                    q++;
                }
            }
        }
        for(int i = 1; i < str.size(); i += 2){ //两个两个查看，最后单独剩余那个被跳过
            if(str[i - 1] == 'j') //j换成i
                str[i - 1] = 'i';
            if(str[i] == 'j') 
                str[i] = 'i';
            int c1 = str[i - 1];
            int c2 = str[i];
            if(c1 == c2) //相等则不变
                continue;
            //找到两个字符在密码表中的位置
            auto index1 = getindex(c1, table);
            int x1 = index1.first;
            int y1 = index1.second;
            auto index2 = getindex(c2, table);
            int x2 = index2.first;
            int y2 = index2.second;
            if(x1 == x2){ //同一行
                y1 = (y1 + 1) % 5;
                y2 = (y2 + 1) % 5;
                str[i - 1] = table[x1][y1];
                str[i] = table[x2][y2];
            }
            else if(y1 == y2){ //同一列
                x1 = (x1 + 1) % 5;
                x2 = (x2 + 1) % 5;
                str[i - 1] = table[x1][y1];
                str[i] = table[x2][y2];
            }
            else{ //取对角
                str[i - 1] = table[x1][y2];
                str[i] = table[x2][y1];
            }
        }
        return str;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$n=max(key\mathrm{.}length,str\mathrm{.}length)n=max(key.length,\; str.length)$，构建密码表遍历字符串key和26个英文字母，虽然只填充26位，加密部分两个字符两个字符地遍历字符串str，因此两边都是一次循环，取较大值
• 空间复杂度：$O(1)O(1)$，辅助数组vis大小为26，密码表大小为25，常数级

方法二：哈希表改进

具体做法：

我们可以在构建密码表的时候，将位置与字符用无序哈希表一一对应，这样后续查找密码表的时候就不用暴力搜索了，直接查找哈希表中的值即可以找到位置。

虽然时间复杂度没有变，但是缩短不少查找的时间。

class Solution {
public:
    string Encode(string key, string str) {
        vector<bool> vis(26, false);
        vector<vector<char> > table(5, vector<char>(5));
        unordered_map<char, pair<int, int> > index;
        int p = 0; //字符串key的指针
        int q = 0; //字母表abcd……的指针
        vis['j' - 'a'] = true; //字母表中没有j
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                if(p < key.length()){
                    if(key[p] == 'j') //j换成i
                        key[p] = 'i';
                    if(!vis[key[p] - 'a']){ //没有出现过的字母才加入
                        vis[key[p] - 'a'] = true;
                        index[key[p]] = make_pair(i, j);
                        table[i][j] = key[p];
                    }else
                        j--; //字符串指针后移，矩阵指针不动
                    p++;
                }else{
                    if(!vis[q]){ //没有出现过的字母才加入
                        index[q + 'a'] = make_pair(i, j);
                        table[i][j] = q + 'a';
                    }else
                        j--; //字符串指针后移，矩阵指针不动
                    q++;
                }
            }
        }
        for(int i = 1; i < str.size(); i += 2){ //两个两个查看，最后单独剩余那个被跳过
            if(str[i - 1] == 'j') //j换成i
                str[i - 1] = 'i';
            if(str[i] == 'j') 
                str[i] = 'i';
            int c1 = str[i - 1];
            int c2 = str[i];
            if(c1 == c2) //相等则不变
                continue;
            int x1 = index[c1].first;
            int y1 = index[c1].second;
            int x2 = index[c2].first;
            int y2 = index[c2].second;
            if(x1 == x2){ //同一行
                y1 = (y1 + 1) % 5;
                y2 = (y2 + 1) % 5;
                str[i - 1] = table[x1][y1];
                str[i] = table[x2][y2];
            }
            else if(y1 == y2){ //同一列
                x1 = (x1 + 1) % 5;
                x2 = (x2 + 1) % 5;
                str[i - 1] = table[x1][y1];
                str[i] = table[x2][y2];
            }
            else{ //取对角
                str[i - 1] = table[x1][y2];
                str[i] = table[x2][y1];
            }
        }
        return str;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$n=max(key\mathrm{.}length,str\mathrm{.}length)n=max(key.length,\; str.length)$，构建密码表遍历字符串key和26个英文字母，虽然只填充26位，加密部分两个字符两个字符地遍历字符串str，因此两边都是一次循环，取较大值
• 空间复杂度：$O(1)O(1)$，辅助数组vis大小为26，密码表大小为25，哈希表大小为26，常数级