796.旋转字符串：暴力模拟

【LetMeFly】796.旋转字符串：暴力模拟

力扣题目链接：https://leetcode.cn/problems/rotate-string/

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

解题方法：暴力模拟

如果两个字符串不等长，则直接返回false。否则(就不需要担心下标越界的问题了)假设字符串长度为$n$：

共计进行$n$次匹配，使用一个变量$diff$从$0$到$n-1$枚举，若存在某个$diff$可以使得$s[(i+diff)\mod n]$和$goal[i]$全部相等，则返回true。

否则返回false。

• 时间复杂度$O(len(s)^2)$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-05-03 17:22:50
 */
class Solution {
private:
    int n;

    bool ok(const string& s, const string& goal, int diff) {
        for (int i = 0; i < n; i++) {
            if (s[(i + diff) % n] != goal[i]) {
                return false;
            }
        }
        return true;
    }
public:
    bool rotateString(const string& s, const string& goal) {
        n = s.size();
        if (goal.size() != n) {
            return false;
        }
        for (int i = 0; i < n; i++) {
            if (ok(s, goal, i)) {
                return true;
            }
        }
        return false;
    }
};

/*
 * @LastEditTime: 2022-04-07 08:13:46
 */
class Solution {
public:
    bool rotateString(string s, string goal) {
        if (s.size() != goal.size())
            return false;
        for (int i = 0; i < s.size(); i++) {
            bool same = true;
            for (int j = 0; j < s.size(); j++) {
                if (s[j] != goal[(i + j) % s.size()]) {
                    same = false;
                    break;
                }
            }
            if (same)
                return true;
        }
        return false;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源