程序员面试金典 - 面试题 01.09. 字符串轮转

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

示例 1:

输入：s1 = "waterbottle", s2 = "erbottlewat"
输出：True

示例 2:

输入：s1 = "aa", s2 = "aba"
输出：False

提示：

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

题目思考

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

解决方案

思路

• s2 如果是 s1 旋转而来, 首先长度肯定要相等, 这是第一个判断
• 接下来分析旋转的特点, 假设 s1 分为 a+b 两部分, s2 就是在 a 和 b 的连接处旋转的, 也即 s2 = b+a, 如何一次判断 s2 满足 b+a 呢?
• 我们可以将 s1 与自身拼接起来, 变成 a+b+a+b, 这样如果 s2 是 b+a, 它一定是拼接字符串的子串, 这样就做到了只调用一次检查子串的方法判断出来

复杂度

• 时间复杂度 O(N): 需要调用一次检查子串的方法
• 空间复杂度 O(N): 需要额外的字符串来存储字符串拼接后的结果

代码

class Solution:
    def isFlipedString(self, s1: str, s2: str) -> bool:
        # 将s1*2, 然后判断s2是否在新的s1里
        # 注意首先要判断两个字符串长度相等
        if len(s1) != len(s2):
            return False
        return s2 in s1 + s1

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊