LeetCode 题解工作台
将单词恢复初始状态所需的最短时间 II
给你一个下标从 0 开始的字符串 word 和一个整数 k 。 在每一秒，你必须执行以下操作： 移除 word 的前 k 个字符。 在 word 的末尾添加 k 个任意字符。 注意 添加的字符不必和移除的字符相同。但是，必须在每一秒钟都执行 两种 操作。 返回将 word 恢复到其 初始 状态所需的…
4
题型
4
代码语言
3
相关题
当前训练重点
困难 · string·结合·rolling·哈希
答案摘要
我们不妨假设，如果只操作一次，就能使得 `word` 恢复到初始状态，那么意味着 `word[k:]` 是 `word` 的前缀，即 `word[k:] == word[:n-k]`。 如果有多次操作，不妨设 为操作次数，那么意味着 `word[k*i:]` 是 `word` 的前缀，即 `word[k*i:] == word[:n-k*i]`。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 string·结合·rolling·哈希 题型思路
题目描述
给你一个下标从 0 开始的字符串 word 和一个整数 k 。
在每一秒，你必须执行以下操作：
- 移除
word的前k个字符。 - 在
word的末尾添加k个任意字符。
注意 添加的字符不必和移除的字符相同。但是，必须在每一秒钟都执行 两种 操作。
返回将 word 恢复到其 初始 状态所需的 最短 时间（该时间必须大于零）。
示例 1：
输入：word = "abacaba", k = 3 输出：2 解释： 第 1 秒，移除 word 的前缀 "aba"，并在末尾添加 "bac" 。因此，word 变为 "cababac"。 第 2 秒，移除 word 的前缀 "cab"，并在末尾添加 "aba" 。因此，word 变为 "abacaba" 并恢复到始状态。 可以证明，2 秒是 word 恢复到其初始状态所需的最短时间。
示例 2：
输入：word = "abacaba", k = 4 输出：1 解释： 第 1 秒，移除 word 的前缀 "abac"，并在末尾添加 "caba" 。因此，word 变为 "abacaba" 并恢复到初始状态。 可以证明，1 秒是 word 恢复到其初始状态所需的最短时间。
示例 3：
输入：word = "abcbabcd", k = 2 输出：4 解释： 每一秒，我们都移除 word 的前 2 个字符，并在 word 末尾添加相同的字符。 4 秒后，word 变为 "abcbabcd" 并恢复到初始状态。 可以证明，4 秒是 word 恢复到其初始状态所需的最短时间。
提示：
1 <= word.length <= 1061 <= k <= word.lengthword仅由小写英文字母组成。
解题思路
方法一：枚举 + 字符串哈希
我们不妨假设，如果只操作一次，就能使得 word 恢复到初始状态，那么意味着 word[k:] 是 word 的前缀，即 word[k:] == word[:n-k]。
如果有多次操作，不妨设 为操作次数，那么意味着 word[k*i:] 是 word 的前缀，即 word[k*i:] == word[:n-k*i]。
因此，我们可以枚举操作次数，利用字符串哈希来判断两个字符串是否相等。
时间复杂度 ，空间复杂度 。其中 为 word 的长度。
class Hashing:
__slots__ = ["mod", "h", "p"]
def __init__(self, s: str, base: int, mod: int):
self.mod = mod
self.h = [0] * (len(s) + 1)
self.p = [1] * (len(s) + 1)
for i in range(1, len(s) + 1):
self.h[i] = (self.h[i - 1] * base + ord(s[i - 1])) % mod
self.p[i] = (self.p[i - 1] * base) % mod
def query(self, l: int, r: int) -> int:
return (self.h[r] - self.h[l - 1] * self.p[r - l + 1]) % self.mod
class Solution:
def minimumTimeToInitialState(self, word: str, k: int) -> int:
hashing = Hashing(word, 13331, 998244353)
n = len(word)
for i in range(k, n, k):
if hashing.query(1, n - i) == hashing.query(i + 1, n):
return i // k
return (n + k - 1) // k
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to optimize the solution using hashing techniques.
- question_mark
Assess the candidate's understanding of prefix-suffix problems and their application to string manipulation.
- question_mark
Evaluate if the candidate can explain how they reduced the complexity of the problem to O(N).
常见陷阱
外企场景- error
Candidates may attempt brute-force approaches, leading to inefficient O(N^2) time complexity.
- error
Failing to use rolling hash may lead to suboptimal solutions for large inputs.
- error
Not properly handling edge cases like when `k` is larger than the string length or when no operation is needed.
进阶变体
外企场景- arrow_right_alt
Instead of a fixed `k`, you could generalize this problem to work with variable values of `k` for different test cases.
- arrow_right_alt
Consider adding a constraint where the string may contain special characters or digits, complicating the prefix-suffix matching.
- arrow_right_alt
Instead of finding the smallest number of seconds, the problem could require finding the number of seconds needed to make the string reach any specific target state.