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

接上文我们继续来分享第二种解题思路方法二搜索子字符串思路和算法首先如果 s 和 goal 的长度不一样那么无论怎么旋转s 都不能得到 goal 返回 false 。字符串 ss 包含了所有 s 可以通过旋转操作得到的字符串只需要检查 goal 是否为 ss 的子字符串即可。具体可以参考「28. 实现 strStr() 的官方题解」的实现代码本题解中采用直接调用库函数的方法代码Python3class Solution: def rotateString(self, s: str, goal: str) - bool: return len(s) len(goal) and goal in s sJavaclass 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); } }Cclass Solution { public: bool rotateString(string s, string goal) { return s.size() goal.size() (s s).find(goal) ! string::npos; } };Cbool 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; }JavaScriptvar rotateString function(s, goal) { return s.length goal.length (s s).indexOf(goal) ! -1; };Golangfunc rotateString(s, goal string) bool { return len(s) len(goal) strings.Contains(ss, goal) }复杂度分析时间复杂度O(n) 其中 n 是字符串 s 的长度。KMP 算法搜索子字符串的时间复杂度为 O(n) 其他搜索子字符串的方法会略有差异。空间复杂度O(n) 其中 n 是字符串 s 的长度。KMP 算法搜索子字符串的空间复杂度为 O(n) 其他搜索子字符串的方法会略有差异。