796. 旋转字符串
796. 旋转字符串
题目
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
andgoal
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)
,因为需要额外的空间来存储拼接后的字符串。
思路二:模拟旋转法
长度检查:
- 首先检查
s
和goal
的长度。如果两者长度不同,则不可能通过旋转操作得到相等的字符串,直接返回false
。
- 首先检查
旋转操作模拟:
- 遍历字符串
s
的每个位置i
,模拟一次旋转操作:- 使用
s.slice(i)
获取从位置i
到结束的子字符串。 - 使用
s.slice(0, i)
获取从开头到位置i
的子字符串。 - 将这两个子字符串连接起来,形成旋转后的字符串。
- 使用
- 检查这个旋转后的字符串是否等于
goal
。如果找到匹配,返回true
。
- 遍历字符串
未找到匹配:
- 如果遍历结束后仍然没有找到匹配的旋转字符串,则返回
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;
};