二、数据结构

二、数据结构

2.1图

算法笔试模拟题精解之“变换的密钥”

贡献者 | 黄信旭

简介：根据题意，只要根据给出的初始关系，计算出对于每个字母可以变成的字

母，就可以直接判断 s1 能不能转化成 s2 了。对于求幂操作有可以加快计算的方法，

叫做矩阵快速幂。这里用求数的次幂举例。

题目描述

题目等级：中等

知识点：广度优先搜索 /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) 一个二维数组保存当前结果，一个保存相乘后的结果。

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