经典算法实例：旋转字符串（二）

接上文，我们继续来分享第二种解题思路：

方法二：搜索子字符串

思路和算法

首先，如果 s 和 goal 的长度不一样，那么无论怎么旋转，s 都不能得到 goal ，返回 false 。字符串 s+s 包含了所有 s 可以通过旋转操作得到的字符串，只需要检查 goal 是否为 s+s 的子字符串即可。具体可以参考「28. 实现 strStr() 的官方题解」的实现代码，本题解中采用直接调用库函数的方法

代码

Python3

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

Java

class Solution { public boolean rotateString(String s, String goal) { return s.length() == goal.length() && (s + s).contains(goal); } }

C#

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

C++

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

C

bool rotateString(char * s, char * goal){ int m = strlen(s), n = strlen(goal); if (m != n) { return false; } char * str = (char *)malloc(sizeof(char) * (m + n + 1)); sprintf(str, "%s%s", goal, goal); return strstr(str, s) != NULL; }

JavaScript

var rotateString = function(s, goal) { return s.length === goal.length && (s + s).indexOf(goal) !== -1; };

Golang

func rotateString(s, goal string) bool { return len(s) == len(goal) && strings.Contains(s+s, goal) }

复杂度分析

时间复杂度：O(n) ，其中 n 是字符串 s 的长度。KMP 算法搜索子字符串的时间复杂度为 O(n) ，其他搜索子字符串的方法会略有差异。

空间复杂度：O(n) ，其中 n 是字符串 s 的长度。KMP 算法搜索子字符串的空间复杂度为 O(n) ，其他搜索子字符串的方法会略有差异。