class Solution {
public:
int minimumTimeToInitialState(string word, int k) {
}
};
3029. 将单词恢复初始状态所需的最短时间 I
给你一个下标从 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 <= 501 <= k <= word.lengthword仅由小写英文字母组成。原站题解
java 解法, 执行用时: 1 ms, 内存消耗: 41.4 MB, 提交时间: 2024-02-06 09:53:23
class Solution {
public int minimumTimeToInitialState(String S, int k) {
char[] s = S.toCharArray();
int n = s.length;
int[] z = new int[n];
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
if (i <= r) {
z[i] = Math.min(z[i - l], r - i + 1);
}
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
l = i;
r = i + z[i];
z[i]++;
}
if (i % k == 0 && z[i] >= n - i) {
return i / k;
}
}
return (n - 1) / k + 1;
}
}
golang 解法, 执行用时: 5 ms, 内存消耗: 2.2 MB, 提交时间: 2024-02-06 09:52:56
func minimumTimeToInitialState(s string, k int) int {
n := len(s)
z := make([]int, n)
for i, l, r := 1, 0, 0; i < n; i++ {
if i <= r {
z[i] = min(z[i-l], r-i+1)
}
for i+z[i] < n && s[z[i]] == s[i+z[i]] {
l, r = i, i+z[i]
z[i]++
}
if i%k == 0 && z[i] >= n-i {
return i / k
}
}
return (n-1)/k + 1
}
python3 解法, 执行用时: 45 ms, 内存消耗: 16.3 MB, 提交时间: 2024-02-06 09:52:39
# Z变换，KMP扩展
class Solution:
def minimumTimeToInitialState(self, s: str, k: int) -> int:
n = len(s)
z = [0] * n
l = r = 0
for i in range(1, n):
if i <= r:
z[i] = min(z[i - l], r - i + 1)
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
l, r = i, i + z[i]
z[i] += 1
if i % k == 0 and z[i] >= n - i:
return i // k
return (n - 1) // k + 1