搜索子字符串的思路与算法分享

我们思考一个问题：

首先，如果 s 和 goal 的长度不一样，那么无论怎么旋转，s 都不能得到 goal ，返回 false 。字符串 s+s 包含了所有 s 可以通过旋转操作得到的字符串，只需要检查 goal 是否为 s+s 的子字符串即可。

代码

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) ，其他搜索子字符串的方法会略有差异。

好了，今天的文章分享就到这里了，希望对大家的学习有帮助哦！