🍥

Hang Zhang

genius.

Data Structure and Algorithm

Rotate String

796. 旋转字符串

分析

s + s 包含 s 所有可能的旋转结果，把 s + s 作为一个整体，在其中查找是否存在 goal 子串

时间复杂度

时间复杂度 O(n)，find 操作在最坏情况下是 O(n^2)，但在实际实现中通常会做优化

空间复杂度

空间复杂度 O(n)

C++代码

1
2
3
4
5
6
7
8
9


class Solution
{
public:
    bool rotateString(string s, string goal)
    {
        // 判断长度是否相等，并且 goal 是否是 s + s 的子串
        return s.size() == goal.size() && (s + s).find(goal) != std::string::npos;
    }
};