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])
1
2
3

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

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

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, -1
    for i in range(1, n):
        if i > r:
            l, r = i, i
            while r < n and s[r-l] == s[r]:
                r += 1
            z[i] = r-l
            r -= 1
        else:
            k = i - l
            if z[k] < r - i + 1:
                z[i] = z[k]
            else:
                l = i
                while r < n and s[r-l] == s[r]:
                    r += 1
                z[i] = r-l
                r -= 1
    z[0] = n
    return z

def find_all(s, t):
    l, n = len(s), len(t)
    prefix = z_algorithm(t)
    nxt, m = n, 0
    for i in range(1, n):
        if i + prefix[i] == n:
            nxt = i
            m = prefix[i]
            break

    idx = 0
    cnt = 0
    while idx < l:
        idx = s.find(t, idx)
        if idx == -1:
            break
        cnt += 1
        if nxt < n:
            while idx+n < l and t[m:] == s[idx+n:idx+n+nxt]:
                idx = idx+nxt
                cnt += 1
        idx += 1
    return cnt
        

class Solution:
    def numberOfWays(self, s: str, t: str, k: int) -> int:
        MOD = 10**9+7
        
        n = len(s)
        m = find_all(s+s[:-1], t)
        
        f0 = 0 if s != t else 1
        fk = f0 * pow(-1, k) + m * pow(n, -1, MOD) * (pow(n-1, k, MOD) - pow(-1, k))
        return fk % MOD
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

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

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