Leetcode 2851. String Transformation

• Leetcode 2851. String Transformation
  • 0. 吐槽
  • 1. 算法思路
    • 1. 整体思路
    • 2. 字符串匹配优化
  • 2. 代码实现

• 题目链接：2851. String Transformation

0. 吐槽

这道题多少有点坑爹，题目本身挺有意思的，是一道数组题目，其实用数学方法直接可以写出结果的数学表达式，因此做的时候成就感非常强。

但是，坑爹的来了，谁会想到这道题最终卡人的是数组匹配算法，真心晕菜！！！

举个不太恰当的例子，就像是你去复原一个魔方，你想了n久，终于想到了魔方的复原方法，然后到了考场上面，面试官给了你一块木头和一把锯子，让你先做个魔方然后再复原，还限时2h……

就尼玛坑爹啊！！！

不过万幸，总算是搞定了，顺道也优化了一下字符串的匹配算法，虽然非我所愿，但多少也有点成就感吧……

1. 算法思路

1. 整体思路

这一题整体思路上可以视为一道数组题目。

显然的，对于一个长度为$n$的字符串s，我们经过$k$此操作之后可能的操作方式总数有$(n-1{)}^k$种。

我们假设第$k$次操作之后字符串s恰好变为t的操作方式总数为$a_k$，那么显然我们有如下递推公式：

$$\begin{array}{rl}{a}_k& =a_{k-1}\times (m-1)+((n-1{)}^{k-1}-a_{k-1})\times m\\ & =m\cdot (n-1{)}^{k-1}-a_{k-1}\end{array}$$

其中，$m$表示s的所有循环字符串（至多经过一次操作之后得到的字符串）当中t的个数，亦即，s可以通过$m$种旋转方式直接变为t。

此时，我们由上述递推公式，不难迭代写出：

$$\begin{array}{rl}{a}_k& =m\cdot (n-1{)}^{k-1}-a_{k-1}\\ a_{k-1}& =m\cdot (n-1{)}^{k-2}-a_{k-2}\\ \cdots & \\ a_1& =m\cdot (n-1{)}^0-a_0\end{array}$$

我们分别带入之后即可得到$a_k$的表达式如下：

$$\begin{array}{rl}{a}_k& =(-1{)}^k{a}_0+m\sum _{i=0}^{k-1}(-1{)}^{k-1-i}\cdot (n-1{)}^i\\ & =(-1{)}^k{a}_0+m\cdot \frac{(n-1{)}^k-(-1{)}^k}{n}\end{array}$$

因此，事实上这道题我们可以通过$n,m,k$的值直接算出我们的最终答案。

剩下的问题就是$n,m$的求解了，其中$n$是显然的，剩下的就是$m$的求解了，本来其实就是将s再拼接一份然后看一下新组成的这个字符串当中t一共出现的次数就行了，用伪代码表示就是：

n = len(s)
ns = s + s[:-1]
m = len([i for i in range(n) if ns[i:i+n] == t])

结果没想到这里居然一直超时，最后这道题大部分的时候居然都集中在了解决这个问题上面，也是醉了……

下面，我们就来看一下我们具体对于这个问题的优化。

2. 字符串匹配优化

如前所述，这里事实上我们可以将问题抽象为如下问题：

已知两个字符串s和t，问s当中t一共出现过多少次。

因此这里其实就是一个字符串匹配的问题，不过我们可以对其进行一下优化：

• 如果s当中的某一段已经和t匹配上了（假设起始坐标为i），此时我们就可以通过t本身的特性，找到t当中最接近头部的某个位置idx，满足t[idx:] == t[:n-idx]，此时我们可以直接跳转到这个位置，然后比较子串t[n-idx:]与s[i+n:i+n+idx]是否一致即可判断新的这个子串s[i+idx:i+idx+n]是否等于t，而无需判断中间的位置以及完整地判断这两个子串是否相同。

此时，问题就简化到了如何求得t当中最接近头部的某个位置idx，满足t[idx:] == t[:n-idx]，而这个可以通过z-algorithm来进行快速实现，关于这部分的内容，我们之前已经写过了一个博客（经典算法：Z算法（z algorithm））对其进行过整理了，这里我们就不再展开赘述了。

2. 代码实现

综上，我们就可以给出我们最终的python代码实现如下：

def z_algorithm(s):n = len(s)z = [0 for _ in range(n)]l, r = -1, -1for i in range(1, n):if i > r:l, r = i, iwhile r < n and s[r-l] == s[r]:r += 1z[i] = r-lr -= 1else:k = i - lif z[k] < r - i + 1:z[i] = z[k]else:l = iwhile r < n and s[r-l] == s[r]:r += 1z[i] = r-lr -= 1z[0] = nreturn zdef find_all(s, t):l, n = len(s), len(t)prefix = z_algorithm(t)nxt, m = n, 0for i in range(1, n):if i + prefix[i] == n:nxt = im = prefix[i]breakidx = 0cnt = 0while idx < l:idx = s.find(t, idx)if idx == -1:breakcnt += 1if nxt < n:while idx+n < l and t[m:] == s[idx+n:idx+n+nxt]:idx = idx+nxtcnt += 1idx += 1return cntclass Solution:def numberOfWays(self, s: str, t: str, k: int) -> int:MOD = 10**9+7n = len(s)m = find_all(s+s[:-1], t)f0 = 0 if s != t else 1fk = f0 * pow(-1, k) + m * pow(n, -1, MOD) * (pow(n-1, k, MOD) - pow(-1, k))return fk % MOD

提交代码评测得到：耗时801ms，占用内存41.1MB。

值得一提的是，截至23.9.10晚间，当前这个执行效率远远高于其他python提交的算法执行效率（其他实现当中最快的执行时间为3167ms），多少也是让我感觉挺有成就感的……