跳至主要內容

796. 旋转字符串


796. 旋转字符串open in new window

🟢   🔖  字符串 字符串匹配  🔗 力扣open in new window LeetCodeopen in new window

题目

Given two strings s and goal, return true if and only if s can become goal after some number ofshifts on s.

A shift on s consists of moving the leftmost character of s to the rightmost position.

  • For example, if s = "abcde", then it will be "bcdea" after one shift.

Example 1:

Input: s = "abcde", goal = "cdeab"

Output: true

Example 2:

Input: s = "abcde", goal = "abced"

Output: false

Constraints:

  • 1 <= s.length, goal.length <= 100
  • s and goal consist of lowercase English letters.

题目大意

给定两个字符串, sgoal。如果在若干次旋转操作之后,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
  • sgoal 由小写英文字母组成

解题思路

思路一:字符串拼接法

  • 首先检查 sgoal 的长度。如果两者长度不同,则不可能通过旋转操作得到相等的字符串,直接返回 false
  • s 拼接到自己,例如 s + s,然后检查 goal 是否是这个拼接字符串的子串。

复杂度分析

  • 时间复杂度O(n),其中 n 是字符串 s 的长度,拼接和比较字符串的时间复杂度为 O(n)
  • 空间复杂度O(n),因为需要额外的空间来存储拼接后的字符串。

思路二:模拟旋转法

  1. 长度检查

    • 首先检查 sgoal 的长度。如果两者长度不同,则不可能通过旋转操作得到相等的字符串,直接返回 false
  2. 旋转操作模拟

    • 遍历字符串 s 的每个位置 i,模拟一次旋转操作:
      • 使用 s.slice(i) 获取从位置 i 到结束的子字符串。
      • 使用 s.slice(0, i) 获取从开头到位置 i 的子字符串。
      • 将这两个子字符串连接起来,形成旋转后的字符串。
    • 检查这个旋转后的字符串是否等于 goal。如果找到匹配,返回 true
  3. 未找到匹配

    • 如果遍历结束后仍然没有找到匹配的旋转字符串,则返回 false

复杂度分析

  • 时间复杂度O(n^2),其中 n 是字符串 s 的长度。在最坏的情况下,需要进行 n 次循环,每次循环又需要 O(n) 的时间来拼接和比较字符串。
  • 空间复杂度O(n),因为在每次旋转操作中,我们都创建了新的子字符串用于比较。

代码

字符串拼接法
/**
 * @param {string} s
 * @param {string} goal
 * @return {boolean}
 */
var rotateString = function (s, goal) {
	if (s.length !== goal.length) return false;
	return (s + s).indexOf(goal) !== -1;
};