破译密码

描述
 牛牛收到了一个任务，任务要求牛牛破译一个密码。牛牛将被给予两个字符串s1和s2，均由四个小写字母构成。需要破译的密码为从s1变换到s2最少需要的变换次数。
 变换的方式是这样：每次变换可以选择当前字符串中的一个位置，然后剩下的三个位置的字符从左到右分别加上2，3，5，若是超出'z'，则重新从'a'开始，例如：对于字符串"abcd"，我们选择'c'的位置进行变换，则变换之后的字符串为"ceci";对于字符串"qyzr",我们选择'r'位置进行变换，则变换之后的字符串为"sber"。
示例
输入："aaaa","ccgk"
返回值：2
说明：第一次变换选择第一个'a'，变成"acdf"，第二次变换选择第二个'c'，变成"ccgk"，故答案为2

方法一

图解+思路分析



    根据图形可以看到本题是一个四叉树，每个节点为字符串中的一个位置，然后剩下的三个位置的字符从左到右分别加上2，3，5变换后的字符串，因此可以利用广度优先搜索，设置队列存放字符串，设置标志数组标记字符串是否访问过，那么s1变换到s2最少需要的变换次数就是四叉树的层数

核心代码 

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最终的答案
     * @param s1 string 表示初始的字符串
     * @param s2 string 表示目标的字符串
     * @return int
     */
	Set<String> index = new HashSet();//不会有重复元素
    Queue<String> q = new LinkedList();//增加删除的效率高
public int solve(String s1, String s2) {
    if(s1 == s2) return 0;
    q.offer(s1);
    int count = 0;
    while(!q.isEmpty()) 
       {
        int size = q.size();
       for(int j=size;j>0;j--)
       {
            String cur = q.poll();
            if(cur.equals(s2)) return count;
            if(index.contains(cur)) continue;//当前字符串已经访问过进行下次循环
            else index.add(cur);//如果没有访问过则进行标记
            for(int i = 0; i < 4; i++)
            {
                String c=convert(cur,i);
                if(!index.contains(c))//变换后的字符串未在index中
                    q.offer(c);//变换后的字符串    加入到队列中
            }
                
        }
        count++;
    }
    return count;
}

public String convert(String s, int i) {
    char[] str = s.toCharArray();
	int[] add = new int[] {2,3,5};
    int index = 0;
    for(int j = 0; j < 4; j++) {
        if(j == i) continue;
        str[j] = (char)('a' + (str[j] - 'a' + add[index]) % 26);
        index++;
    }
    return String.valueOf(str);
}
}

复杂度分析

  • 时间复杂度：需要访问队列中的字符串，总的字符串为$O(26^4)$，时间复杂度为$O(26^4)$，因此时间复杂度为$O(1)$
  • 空间复杂度：需要使用队列和标记数组，空间复杂度为$O(26^4)$，因此总的空间复杂度为$O(1)$

方法二

图解+思路分析



根据方法一中的二叉树，我们将其转换为数字表示，可以看到固定一个位置，其他位置可以进行加法操作，因此有四种情况，分别为:
  • 固定第一个位置，设置固定次数为$i$，后面三个位置的字符加2、3、5，那么表示为$s1[1]+=2*i、s1[2]+=3*i、s1[3]+=5*i$
  • 固定第二个位置，设置固定次数为$j$，其余三个位置从左至右的字符加2、3、5，那么表示为$s1[0]+=2*j、s1[2]+=3*j、s1[3]+=5*j$
  • 固定第三个位置，设置固定次数为$k$，其余三个位置从左至右的字符加2、3、5，那么表示为$s1[0]+=2*k、s1[1]+=3*k、s1[3]+=5*k$
  • 固定第四个位置，设置固定次数为$l$，其余三个位置从左至右的字符加2、3、5，那么表示为$s1[0]+=2*l、s1[1]+=3*l、s1[2]+=5*l$
因此四层循环得到变换后的字符串为：
  • $s1[0]+=2*j+2*k+2*l$
  • $s1[1]+=2*i+3*k+3*l$
  • $s1[2]+=3*i+3*j+5*l$
  • $s1[3]+=5*i+5*j+5*k$
因此每次比较变换后的字符串与字符串s2，如果一致则更新变换的次数，变换的次数即为$（i+k+j+l）$，最后输出最小的变换次数

核心代码 

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最终的答案
     * @param s1 string 表示初始的字符串
     * @param s2 string 表示目标的字符串
     * @return int
     */
    int solve(string s1, string s2) {
        // write code here
        if(s1==s2) return 0;
        vector<int> distance(4,0);
        for(int i=0;i<4;i++)
        {
            distance[i]=(s2[i] - s1[i] + 26) % 26;
        }
       int count = 26 * 4;
        //四层嵌套循环
       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(distance[0] == (2*j + 2*k + 2*l) % 26 && distance[1] == (2*i + 3* k + 3*l) % 26 && distance[2] == (3*i + 3*j + 5*l) % 26 && distance[3] == 5*(i + j + k) % 26)
                 count = min(count, i + j + k + l);
       return count;
    }
};

复杂度分析

  • 时间复杂度：每个位置的字符选择有26种，每个字符串一共有4个字符，四层循环遍历，每一层循环遍历的次数为26，总的时间复杂度为$O(26^4)$，因此时间复杂度为$O(1)$
  • 空间复杂度：空间复杂度为$O(1)$