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

总结

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