796. 旋转字符串

🟢   🔖  字符串 字符串匹配  🔗 力扣 LeetCode

题目

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.

题目大意

给定两个字符串, 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 由小写英文字母组成

解题思路

思路一：字符串拼接法

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

复杂度分析

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

思路二：模拟旋转法

1. 长度检查：

   • 首先检查 s 和 goal 的长度。如果两者长度不同，则不可能通过旋转操作得到相等的字符串，直接返回 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;
};

模拟旋转法

/**
 * @param {string} s
 * @param {string} goal
 * @return {boolean}
 */
var rotateString = function (s, goal) {
	if (s.length !== goal.length) return false;
	for (let i = 0; i < s.length; i++) {
		if (s.slice(i) + s.slice(0, i) == goal) {
			return true;
		}
	}
	return false;
};