程序员面试金典 - 面试题 01.09. 字符串轮转题目难度:简单原题链接[1]今天

题目难度: 简单
原题链接[1]
今天继续更新程序员面试金典系列, 大家在公众号算法精选里回复面试金典就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述字符串轮转。给定两个字符串 s1 和 s2 ，请编写代码检查 s2 是否为 s1 旋转而成（比如， waterbottle 是 erbottlewat 旋转后的字符串）。
示例 1:输入：s1 = "waterbottle", s2 = "erbottlewat" 输出：True
示例 2:【程序员面试金典 - 面试题 01.09. 字符串轮转】输入：s1 = "aa", s2 = "aba" 输出：False
提示：字符串长度在[0, 100000]范围内。
题目思考

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

解决方案思路

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 Falsereturn s2 in s1 + s1

参考资料[1]
原题链接: