题解 | #破译密码#

题意整理

给定字符串s1和s2，均由4个字母组成。
求s1变换到s2，至少要变换多少次。
变换的规则是，固定其中一位，其他三位从左到右依次加上2、3和5，如果超过'z'，重新从'a'开始。

方法一（BFS）

1.解题思路

初始化一个队列和set，队列用于存储每次变化的字符串和当前变换的次数，set用于去重，如果已经在队列，则不会再入队。
每次判断当前字符串是否等于目标字符串，如果是，则直接返回变换次数。如果不是，则寻找当前字符串可能变换出的所有字符串，加入到队列。
寻找可能的字符串按照题目规则进行模拟。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最终的答案
     * @param s1 string 表示初始的字符串
     * @param s2 string 表示目标的字符串
     * @return int
     */
    public int solve (String s1, String s2) {
        //初始化队列，队列里的元素由当前String和步数step组成
        LinkedList<Pair> queue=new LinkedList<>();
        queue.offer(new Pair(s1,0));
        //初始化set，用于去重
        Set<String> set=new HashSet<>();
        set.add(s1);
        while(!queue.isEmpty()){
            //取出当前元素
            Pair pair=queue.poll();
            String curString=pair.s;
            int curStep=pair.step;
            //如果等于s2，说明破译了密码，直接返回step
            if(curString.equals(s2)){
                return curStep;
            }
            //找到经过变换后可能存在的所有字符串
            String[] next=getNext(curString);
            for(String ss:next){
                //如果不在set，则放入队列
                if(!set.contains(ss)){
                    queue.offer(new Pair(ss,curStep+1));
                    set.add(ss);
                }
            }
        }

        return -1;
    }

    //找到经过变换后可能存在的所有字符串
    private String[] getNext(String s){
        String alpha="abcdefghijklmnopqrstuvwxyz";
        String[] res=new String[4];
        for(int i=0;i<4;i++){
            StringBuilder sb=new StringBuilder();
            //固定0位置时，1、2、3位置分别加2、3、5
            if(i==0){
                int index1=(s.charAt(1)-'a'+2)%26;
                int index2=(s.charAt(2)-'a'+3)%26;
                int index3=(s.charAt(3)-'a'+5)%26;
                sb.append(s.charAt(0))
                  .append(alpha.charAt(index1))
                  .append(alpha.charAt(index2))
                  .append(alpha.charAt(index3));
                res[i]=sb.toString();
            }
            //固定1位置时，0、2、3位置分别加2、3、5
            if(i==1){
                int index0=(s.charAt(0)-'a'+2)%26;
                int index2=(s.charAt(2)-'a'+3)%26;
                int index3=(s.charAt(3)-'a'+5)%26;
                sb.append(alpha.charAt(index0))
                  .append(s.charAt(1))
                  .append(alpha.charAt(index2))
                  .append(alpha.charAt(index3));
                res[i]=sb.toString();
            }
            //固定2位置时，0、1、3位置分别加2、3、5
            if(i==2){
                int index0=(s.charAt(0)-'a'+2)%26;
                int index1=(s.charAt(1)-'a'+3)%26;
                int index3=(s.charAt(3)-'a'+5)%26;
                sb.append(alpha.charAt(index0))
                  .append(alpha.charAt(index1))
                  .append(s.charAt(2))
                  .append(alpha.charAt(index3));
                res[i]=sb.toString();
            }
            //固定3位置时，0、1、2位置分别加2、3、5
            if(i==3){
                int index0=(s.charAt(0)-'a'+2)%26;
                int index1=(s.charAt(1)-'a'+3)%26;
                int index2=(s.charAt(2)-'a'+5)%26;
                sb.append(alpha.charAt(index0))
                  .append(alpha.charAt(index1))
                  .append(alpha.charAt(index2))
                  .append(s.charAt(3));
                res[i]=sb.toString();
            }
        }

        return res;
    }

}

//当前String和步数组成的类
class Pair{
    String s;
    int step;

    Pair(String s,int step){
        this.s=s;
        this.step=step;
    }
}

3.复杂度分析

时间复杂度：总共可能有 $26^4$ 个不同的字符串，所以时间复杂度是 $O(1)$ 。
空间复杂度：最坏情况下，需要额外 $26^4$ 大小的队列，所以空间复杂度是 $O(1)$ 。

方法二（枚举）

1.解题思路

首先统计每个位置的变换次数。
然后四层循环，枚举所有位置的固定次数，如果变换次数等于对应位置需要的变换次数，则对应的固定次数就是正确的破解方式，而固定次数之和即是所求的变换次数，取最小值即可。

举例说明：

比如固定j位置时，i位置一定是加2，固定k位置，i也必定是加2，固定l位置时，i还是加2，所以需要满足 $2*(j+k+l)==delta[0]$ 这个等式，才能到达目标字符串。再比如固定i时，j位置需要加2，固定k时，j位置需要加3，固定l时，j位置还是需要加3，所以需要满足 $2*i+3*(k+l)==delta[1]$ 这个等式。同理还需要满足 $3*(i+j)+5*l==delta[2]$ 和 $5*(i+j+k)==delta[3]$ 。由于超过'z'需要重新从'a'开始，所以每次要对26取余。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最终的答案
     * @param s1 string 表示初始的字符串
     * @param s2 string 表示目标的字符串
     * @return int
     */
    public int solve (String s1, String s2) {
        //初始化变换数组
        int[] delta=new int[4];
        for(int i=0;i<4;i++){
            //统计每一位总共需要变换多少次
            delta[i]=(s2.charAt(i)-s1.charAt(i)+26)%26;
        }
        //用于记录最小变换次数
        int res=100;
        //枚举每个位置的固定次数
        for(int i=0;i<26;i++){
            for(int j=0;j<26;j++){
                for(int k=0;k<26;k++){
                    for(int l=0;l<26;l++){
                        //固定某个位置对应的变化次数
                        if((2*(j+k+l))%26==delta[0]
                          &&(2*i+3*(k+l))%26==delta[1]
                          &&(3*(i+j)+5*l)%26==delta[2]
                          &&(5*(i+j+k))%26==delta[3]){
                            //4个位置固定次数之和，即是总变换次数
                            res=Math.min(res,i+j+k+l);
                        }
                    }
                }
            }
        }
        return res;
    }

}

3.复杂度分析

时间复杂度：总共可能有 $26^4$ 个不同的字符串，所以时间复杂度是 $O(1)$ 。
空间复杂度：最坏情况下，需要额外 $26^4$ 大小的队列，所以空间复杂度是 $O(1)$ 。