将单词恢复初始状态所需的最短时间 I

难度: Medium

给你一个下标从 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 <= 50
1 <= k <= word.length
word仅由小写英文字母组成。

Submission

运行时间: 15 ms

内存: 16.2 MB

class Solution:
    def minimumTimeToInitialState(self, word: str, k: int) -> int:
        n = len(word)
        ans = math.ceil(n / k)
        print(ans, math.gcd(n, k))
        for i in range(k, n, k):
            if word[i:] == word[:n-i]:
                print(i, i//k )
                return i // k
        return ans

Explain

本题解通过判断字符串的旋转周期来解决问题。首先计算将整个字符串翻转一遍所需要的最少次数，即 n / k 上取整。然后，从 k 位置开始，以 k 为步长，检查 word 的后缀是否与 word 的前缀相匹配。如果在某个点 i 处，word[i:]（即从 i 开始到末尾的子串）与 word[:n-i]（即从开头到 n-i 位置的子串）相同，这说明找到了一个周期，word 可以在 i // k 次操作后恢复到初始状态。如果没有找到这样的周期，返回 n / k 的上取整结果。

时间复杂度: O(n^2 / k)

空间复杂度: O(1)

class Solution:
    def minimumTimeToInitialState(self, word: str, k: int) -> int:
        n = len(word)  # word的长度
        ans = math.ceil(n / k)  # 计算最少需要完整循环的次数
        for i in range(k, n, k):  # 从k开始以k为步长遍历
            if word[i:] == word[:n-i]:  # 检查后缀是否与前缀匹配
                return i // k  # 如果匹配，返回所需的最短时间
        return ans  # 如果没有找到匹配，返回最初计算的次数

Explore

此问题似乎与题解中描述的算法不完全相关，因为算法没有涉及到字符的添加与移除，而是基于字符串旋转和周期性检查的逻辑。可能是对题目描述的误解。题目可能指的是在某些操作中允许某种形式的重组以探测字符串的周期性，但具体细节需要根据题目的完整描述来确认。

使用`math.ceil(n / k)`是为了确保在所有字符都能至少被覆盖一次的情况下计算最少的操作次数。即使当`n % k ≠ 0`时，也就是说`k`不能整除`n`，最后一个操作可能只处理剩余的少于`k`的字符，但依然需要计算为一个完整的操作次数。因此，使用向上取整确保所有字符至少被处理一次，而不是只处理到`n - n % k`的位置。

从`k`位置开始，以`k`为步长进行检查是基于题目设定的操作方式，即每次操作可以考虑长度为`k`的字符串段。此方法的设计是为了有效地检查在每`k`个字符形成的周期中是否可以通过重复达到初始状态。如果`k`是字符串长度的一个因子，则这种方法不会遗漏周期性匹配；但如果`k`不是因子，则可能需要更复杂的方法来检查非`k`步长的周期性，因此在某些情况下可能会遗漏周期性的匹配。