面试题 01.09. 字符串轮转【暴力模拟】【尾插】

题目

字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。

难度：简单

提示：

1. 字符串长度在[0, 100000]范围内。

说明:

1. 你能只调用一次检查子串的方法吗？

题解

暴力-335ms

按照题意暴力模拟

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        // 特殊情况
        if ("".equals(s2) && s1.equals(s2)) {
            return true;
        }
        // 如果长度不相等
        if (s1.length() != s2.length()) {
            return false;
        }
        for (int i = 0; i < s1.length(); i++) {
            if (s1.equals(s2.substring(i) + s2.substring(0, i))) {
                return true;
            }
        }
        return false;
    }
}

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

尾插-0ms

将s2字符串插入s2，如果循环后有s1，那么尾插后的s2中肯定有s1

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length()!=s2.length()){
            return false;
        }
        String str = s2 + s2;
        return str.contains(s1);
    }
}

复杂度分析

• 时间复杂度：O(1)
• 空间复杂度：O(N)