LeetCode题目笔记——01.09. 字符串轮转

题目描述

题目难度——简单

方法一

  首先看两个字符串的长度，如果两个字符串都不一样长，那么无论怎么旋转，两个字符串都不可能一样，直接返回false。然后再考虑特殊情况，比如两个字符串都是空串，那直接返回true。其他正常情况时，我们可以每次从S2的一个位置开始，循环length次进行比较每一位的字符是否相等。这样做的时间复杂度为O(N**2)，空间为O(1)，只用到了两个下标变量。

代码

class Solution {
public:
bool isFlipedString(string s1, string s2) {
if (s1.size() != s2.size()) {
return false;
}
else if (s1.size() < 1) {
return true;
}
bool flag = true;
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (s1[(i + j) % n] != s2[j]) {
flag = false;
break;
}
}
if (flag) {
return true;
}
}
return false;
}
};

方法二——利用额外空间

  如果S1是正常的，S2是旋转后的，那么如果我们将两个S2进行拼接，那么前一个S2的后半部分就会和后一个S2的前半部分组成S1，例如题目中的ttlewatterbo，将它拼起来，我们就得到了ttlewatterbottlewatterbo，可以看到中间就出现了S1，于是我们只需经过一次遍历，就可以找到答案。这样时间复杂度就降到了O(N)，而空间来到了O(N)，因为使用了额外的空间。

代码C++/Python

  自己写代码来进行遍历比较的话，会很慢，每次循环都要调用一次substr函数。

class Solution {
public:
bool isFlipedString(string s1, string s2) {
if(s1.length() != s2.length()){
return false;
}
else if(s1.length() < 1){
return true;
}
bool res = false;
string tmp = s2 + s2;
int length = s1.length();
for(int i = 0; i < length; i++){
if(tmp.substr(i, length) == s1){
res = true;
break;
}
}
return res;
}
};

  于是我们可以用C++的官方查找子字符串函数，这样更快。

class Solution {
public:
bool isFlipedString(string s1, string s2) {
if(s1.size() != s2.size()){
return false;
}
else if(s1.size() < 1){
return true;
}
string tmp = s2 + s2;
return tmp.find(s1) != string::npos;
}
};

class Solution:
def isFlipedString(self, s1: str, s2: str) -> bool:
if len(s1) != len(s2):
return False
elif len(s1) < 1:
return True
return s1 in s2 + s2

总结

  两种方法都需要对字符串进行一次遍历，这是不可避免的，方法二牺牲了空间，比较巧妙。

最后

以上就是洁净汽车为你收集整理的LeetCode题目笔记——01.09. 字符串轮转的全部内容，希望文章能够帮你解决LeetCode题目笔记——01.09. 字符串轮转所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。