在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding

本文为大家介绍其中的第58题：变换的密钥 的题目解析，具体如下：

题目描述

题目等级：中等
知识点：广度优先搜索/BFS、Floyed最短路、图

查看题目：变换的密钥 Tom最开始有一个密钥s1，s1是长度为n的由小写字母组成的字符串。Jerry也有一个长度为n的由小写字母组成的密钥s2。
现在有m组关系，每组关系由两个数字[u,v]构成(1<=u,v<=26)，表示26个字母表中的第u个小写字母可以直接转换为第v个小写字母。
假设u=1，v=2,那么说明字母'a'可以直接转换为字母'b'。现在Tom对于s1的每个字母使用无数次转换，请判断s1能否转换为s2。
输入内容为四部分，第一部分为n(1<=n<=100000)，代表字符串的长度。接下来两部分分别是长度为n的s1,s2。
第四部分为m（1 <=m <=325），代表关系个数。接下来是m组[u,v]关系。
如果s1能变成s2,则输出YES,否则输出NO。
示例1
输入：
6
"aabbcc"
"cdbcad"
4
[[1,3],[3,1],[1,4],[2,3]]
输出：
"YES"
注意
可以转换多次，比如a可以转换为b，而b可以转换为c，则a可以转换为c。
样例：aabbcc->cabbcc->cdbbcc->cdbccc->cdbcac->cdbcaa->cdbcad

解题思路一：一般思路

根据题意，只要根据给出的初始关系，计算出对于每个字母可以变成的字母，就可以直接判断s1能不能转化成s2了。
例如样例中计算过后

a -> a,c,d
b -> b,c
c -> a,c,d
d -> d

对于这个结果，可以使用一个26*26的二维数组change来保存。每一行表示原始字母，每一列表示可以变换成的字母。1表示可以变化，0表示不能变换。
计算过程：
1． 初始化，根据给出的关系填充数组
2． 记得数组对角线要填为1，表示每个字母可以不进行变换，是自己本身。
3． 计算经过无数次变换后的数组。

对于第三步可以直接进行多次for循环，因为数组不大，一般不会超时。

方法二：矩阵快速幂

经过0-2次变换后可以达到的字母的结果相当于change*change，0-3次对应的相当于change*change*change，0-n次对应的就是change^n。这是一个矩阵求幂的过程。

对于求幂操作有可以加快计算的方法，叫做矩阵快速幂。这里用求数的次幂举例。

假设要求 x^13。直接的方法是进行12次相乘。
我们可以观察到13 = 8 + 4 + 1= 2^3 + 2^2 + 1
所以x^13 = x^8 + x^4 + x= (x^4)^2 + (x^2)^2 + 0*(x)^2 + x

从右向左，每一项都是前一项的平方。这样原来需要12次乘法的操作变成了3次惩罚，3次加法（第二项系数为0，不用加）。

与求数的次幂类似，矩阵也可以用相同的方法加速计算。对于这道题本身，因为矩阵中非0的结果表示可以进行变换，所以相乘时没有必要算出具体的值，只需要判断结果是否非0。

因为只有26个字母，所以只需要算到26次幂就可以了，也可以计算32次幂来去掉加法的部分。

时间复杂度O(5*26*26*26) 5是求32次幂需要的矩阵乘法次数。26*26*26是一次乘法需要的时间复杂度。
空间复杂度O(2*26*26) 一个二维数组保存当前结果，一个保存相乘后的结果。

看完之后是不是有了想法了呢，快来练练手吧>>查看题目：变换的密钥