Easy

题目描述

给定两个字符串 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。时间复杂度较高。

方法二：字符串拼接（推荐） 这是最巧妙的解法。观察发现，如果 goal 是 s 的旋转结果，那么 goal 一定是 s + s 的子字符串。

例如：s = "abcde"，所有可能的旋转结果都会出现在 "abcdeabcde" 中：

  • "abcde" (0次旋转)
  • "bcdea" (1次旋转)
  • "cdeab" (2次旋转)
  • "deabc" (3次旋转)
  • "eabcd" (4次旋转)

因此，只需要检查两个条件：

  1. s 和 goal 长度相等
  2. goal 是 s + s 的子字符串

这个方法时间复杂度为 O(n)，空间复杂度为 O(n)，是最优解。

代码实现

class Solution {
public:
    bool rotateString(string s, string goal) {
        if (s.length() != goal.length()) {
            return false;
        }
        return (s + s).find(goal) != string::npos;
    }
};

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False
        return goal in s + s

public class Solution {
    public bool RotateString(string s, string goal) {
        if (s.Length != goal.Length) {
            return false;
        }
        return (s + s).Contains(goal);
    }
}

var rotateString = function(s, goal) {
    if (s.length !== goal.length) {
        return false;
    }
    return (s + s).includes(goal);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)字符串拼接 O(n)，子字符串查找平均 O(n)
空间复杂度O(n)需要额外空间存储拼接后的字符串