千问 LeetCode 3031. 将单词恢复初始状态所需的最短时间 II C++实现

针对 LeetCode 3031. 将单词恢复初始状态所需的最短时间 II由于数据规模较大暴力匹配会超时。最优的解法是利用 Z 函数扩展 KMP 来高效判断字符串的后缀是否与前缀匹配。核心思路1. 操作分析每次操作会移除字符串的前 k 个字符并在末尾添加 k 个任意字符。如果经过 t 次操作后字符串恢复初始状态意味着原字符串删除了前 t times k 个字符后剩余的后缀必须与原字符串的前缀完全相同。此时我们在末尾补充的 t times k 个字符可以任意指定为原字符串缺失的前缀部分。2. Z 函数应用Z 函数Z 数组的定义是z[i] 表示从下标 i 开始的后缀与原字符串前缀的最长公共前缀LCP的长度。3. 寻找最短时间- 从小到大枚举操作次数 t即枚举删除的字符数 i t * k。- 如果 z[i] n - i说明从 i 开始的后缀完全匹配原字符串的前缀此时所需时间即为 i / k。- 如果遍历完所有可能的 i 都没有找到匹配的后缀说明必须将原字符串的所有字符全部删除。由于补充的字符可以任意指定此时所需的最短时间为 lceil n / k rceil即 (n k - 1) / k。C 实现代码class Solution {public:int minimumTimeToInitialState(string word, int k) {int n word.size();vectorint z(n, 0);// 1. 计算 Z 函数int l 0, r 0;for (int i 1; i n; i) {// 利用已匹配的区间 [l, r] 进行初始化if (i r) {z[i] min(z[i - l], r - i 1);}// 暴力向后扩展匹配while (i z[i] n word[z[i]] word[i z[i]]) {l i;r i z[i];z[i];}}// 2. 枚举每次删除 k 个字符后的位置for (int i k; i n; i k) {// 如果从 i 开始的后缀长度 (n - i) 完全等于它与原字符串前缀的匹配长度 z[i]if (z[i] n - i) {return i / k;}}// 3. 如果没有任何后缀能匹配前缀则必须删除所有原字符// 向上取整计算操作次数(n k - 1) / kreturn (n k - 1) / k;}};复杂度分析* 时间复杂度O(n)其中 n 为字符串 word 的长度。计算 Z 函数的时间复杂度为 O(n)后续枚举操作次数最多遍历 O(n/k) 次整体时间复杂度为 O(n)。* 空间复杂度O(n)主要用于存储 Z 数组。