0796. 旋转字符串【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 模拟旋转
• 3. 🎯 s.2 - 利用字符串的周期性

1. 📝 题目描述

• leetcode

---

• 给定两个字符串, s 和 goal。
• 如果在若干次旋转操作之后，s 能变成 goal，那么返回 true。
• s 的 旋转操作 就是将 s 最左边的字符移动到最右边。
• 例如, 若 s = 'abcde'，在旋转一次之后结果就是'bcdea'。

---

示例 1：

输入: s = "abcde", goal = "cdeab"
输出: true

示例 2：

输入: s = "abcde", goal = "abced"
输出: false

---

提示：

• 1 <= s.length, goal.length <= 100
• s 和 goal 由小写英文字母组成

2. 🎯 s.1 - 模拟旋转

js

/**
 * @param {string} s
 * @param {string} goal
 * @return {boolean}
 */
var rotateString = function (s, goal) {
  // 长度不同则不可能通过旋转得到
  if (s.length !== goal.length) {
    return false
  }

  // 如果两个字符串相同，直接返回true
  if (s === goal) {
    return true
  }

  // 模拟所有可能的旋转
  let rotated = s
  for (let i = 0; i < s.length; i++) {
    // 执行一次旋转操作：将第一个字符移到末尾
    rotated = rotated.substring(1) + rotated[0]
    if (rotated === goal) {
      return true
    }
  }

  return false
}

• 时间复杂度：$O(n^2)$，其中 n 是字符串的长度，需要进行 n 次旋转，每次旋转和比较需要 $O(n)$ 时间
• 空间复杂度：$O(n)$，每次旋转都需要创建新的字符串

3. 🎯 s.2 - 利用字符串的周期性

js

/**
 * @param {string} s
 * @param {string} goal
 * @return {boolean}
 */
var rotateString = function (s, goal) {
  // 长度不同则不可能通过旋转得到
  if (s.length !== goal.length) {
    return false
  }

  // 空字符串的情况
  if (s.length === 0) {
    return true
  }

  // 如果goal可以通过旋转s得到，那么goal一定是s+s的子串
  return (s + s).includes(goal)
  // return (s + s).indexOf(goal) !== -1
}

• 时间复杂度：$O(n^2)$，其中 n 是字符串的长度，字符串包含检查需要 $O(n^2)$ 时间
• 空间复杂度：$O(n)$，需要创建长度为 2n 的字符串
• 算法思路：巧妙利用字符串的周期性来求解。

字符串 s = "abcde" 的旋转具有周期性：
旋转0次: abcde
旋转1次: bcdea
旋转2次: cdeab
旋转3次: deabc
旋转4次: eabcd
旋转5次: abcde (回到原点)

关键：所有可能的旋转结果都包含在 s+s 中
s+s = "abcdeabcde" 包含了所有旋转状态