建设主管部门官方网站,徐州做网站设计,手机版网站建设价格,国外网站建设什么价格Leetcode 3031. Minimum Time to Revert Word to Initial State II 1. 解题思路2. 代码实现 题目链接#xff1a;3031. Minimum Time to Revert Word to Initial State II
1. 解题思路
这一题就是一个z算法的题目#xff0c;算是比较套路的题目了。
关于z算法#xff0c…Leetcode 3031. Minimum Time to Revert Word to Initial State II 1. 解题思路2. 代码实现 题目链接3031. Minimum Time to Revert Word to Initial State II
1. 解题思路
这一题就是一个z算法的题目算是比较套路的题目了。
关于z算法之前我们已经写过一个博客经典算法Z算法z algorithm对这个经典算法本身进行了一下介绍这里就不展开了有兴趣的读者可以自行跳转去看一下或者网上随便其他找一个介绍文章也可以挺常见的一个算法了。
因此我们就只看一下z算法是如何应用到这道题目就行了。显然由于每次移除前k个字符然后再最后补充k个字符因此如果存在某次移除k个字符之后剩余的子串与原始字符串的开头部分完全一致那么我们只需要在后续进行余留的字符补充即可。
而如果知道删除完一轮都无法找到任何字符它的后续子串恰好为原始字符串开头的部分那么我们也没有关系总可以删完重排的。
因此我们要做的就是求取每一个位置的后续子串与原始子串的最长公共头部序列而这就是z算法要做的事情。
综上我们先调用一次z算法之后用一个while循环遍历一边即可得到最终答案。
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 zclass Solution:def minimumTimeToInitialState(self, word: str, k: int) - int:z z_algorithm(word)ans, idx, n 0, 0, len(word)while True:idx kans 1if idx n or z[idx] n-idx:breakreturn ans提交代码评测得到耗时538ms占用内存21.2MB。
