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 <= 50
• 1 <= k <= word.length
• word仅由小写英文字母组成。

解题思路

首先我们需要先理解一下题目意思，题目要求我们每1秒都要同时执行一次一下操作：

• 移除 word 的前 k 个字符。
• 在 word 的末尾添加 k 个任意字符。

我们以示例 1 word = "abacaba", k = 3来分析一下：

• 第一秒

移除前3个字符，我们可以得到：caba；

在末尾加上任意3个字符，这里我们使用.来代替，我们可以得到：caba...；

无法得到原字符串一样的字符，继续

• 第二秒

移除前3个字符，我们可以得到：a...；

在末尾加上任意3个字符，这里我们使用.来代替，我们可以得到：a......；

可以得到原字符串一样的字符，结束。

在上面例子中我们可以清晰看出，.可以代替任意字符，相当于我们只需要确保前面不是.的字符串和原字符串相同即可,这样我们便可以开始编写代码了。

AC代码

/**
 * @param {string} word
 * @param {number} k
 * @return {number}
 */
var minimumTimeToInitialState = function (word, k) {
  let cnt = 1;
  while (k * cnt < word.length) {
    const tmpWord = word.slice(k * cnt);
    if (word.startsWith(tmpWord)) return cnt;
    cnt++;
  }
  return cnt;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。