示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇围绕 doocs/leetcode 仓库中 lcci/01.09.String Rotation 一题展开讲解“判断s2是否为s1旋转而成”这一经典字符串问题重点推导“长度相等时s2是s1 s1的子串”这一核心等价关系并给出 Python、Java、C、Go、TypeScript、Rust、Swift 七种语言的单行实现。读完本文你将掌握旋转字符串问题的数学本质、s1 s1构造法的证明过程以及各语言子串 API 的细微差异与边界处理。题目背景与描述该题出自《程序员面试金典第 6 版》面试题 01.09属于 doocs/leetcode 仓库 lcci程序员面试金典题解目录下的经典字符串题目。题目要求给定两个字符串s1和s2编写代码检查s2是否为s1旋转而成。所谓“旋转”就是把字符串的某个前缀移动到末尾。例如waterbottle旋转后可得到erbottlewat把前缀wat移到末尾erbottlewat。示例 1输入s1 waterbottle, s2 erbottlewat 输出True示例 2输入s1 aa, s2 aba 输出False约束与提示字符串长度在[0, 100000]范围内即需要考虑空字符串的边界情况额外说明能否只调用一次检查子串的方法这正是s1 s1构造法的用武之地。核心思路把旋转判定转化为一次子串判定第一步长度剪枝旋转操作不会改变字符串长度因此如果s1和s2长度不相等则二者必然不是旋转关系直接返回False。这一剪枝同时天然处理了大部分不匹配的输入避免后续多余的拼接与查找开销。第二步s1 s1覆盖所有旋转情况当s1和s2长度相等时将两个s1连接起来得到s1 s1。这个拼接串一定包含了s1旋转的所有情况原因在于s1的任意旋转都可以表示为s1[i:] s1[:i]把前i个字符移到末尾而在s1 s1中从第i个位置起恰好可以截取到s1[i:] s1[:i]这一子串因为s1 s1的后半段补上了s1[:i]。因此判定s2是否为s1的旋转等价于判定s2是否是s1 s1的子串。整个问题被化简为一次子串查找恰好满足题目“只调用一次检查子串的方法”的要求。图示验证# 成立s2 baa 是 s1 s1 的子串 s1 aba s2 baa s1 s1 abaaba ^^^ # 不成立s2 bab 不是 s1 s1 的子串 s1 aba s2 bab s1 s1 abaaba复杂度分析设n为字符串s1的长度时间复杂度O(n)长度比较为O(1)s1 s1的拼接与子串查找均为线性级别空间复杂度O(n)需要额外的空间存储拼接后的s1 s1字符串。仓库源码七种语言的单行实现doocs/leetcode 在该题目录lcci/01.09.String Rotation/下提供了完整的多语言实现各 Solution 源码文件 与 README 中的代码一一对应。Python3Solution.pyclass Solution: def isFlipedString(self, s1: str, s2: str) - bool: return len(s1) len(s2) and s2 in s1 * 2and短路求值长度不等时直接返回False不会执行s1 * 2的拼接s2 in s1 * 2即一次子串判定。JavaSolution.javaclass Solution { public boolean isFlipedString(String s1, String s2) { return s1.length() s2.length() (s1 s1).contains(s2); } }Java 的String.contains在 JDK 中基于高效的字符串搜索算法实现一次调用即可完成子串判定。CSolution.cppclass Solution { public: bool isFlipedString(string s1, string s2) { return s1.size() s2.size() (s1 s1).find(s2) ! string::npos; } };C 的string::find在未找到时返回string::npos因此需显式比较返回值。(s1 s1)会构造临时对象空间开销为O(n)。GoSolution.gofunc isFlipedString(s1 string, s2 string) bool { return len(s1) len(s2) strings.Contains(s1s1, s2) }Go 的strings.Contains(s, substr)报告substr是否在s中实现简洁直观。TypeScriptSolution.tsfunction isFlipedString(s1: string, s2: string): boolean { return s1.length s2.length (s2 s2).indexOf(s1) ! -1; }注意 TypeScript 实现采用了对称写法拼接s2 s2并检查s1是否为其子串。由于“旋转”是互为关系的s2是s1的旋转当且仅当s1是s2的旋转在长度相等的前提下s2是s1 s1的子串与s1是s2 s2的子串完全等价。indexOf返回-1表示不存在。RustSolution.rsimpl Solution { pub fn is_fliped_string(s1: String, s2: String) - bool { s1.len() s2.len() (s2.clone() s2).contains(s1) } }Rust 实现同样采用s2 s2的对称写法。细节上(s2.clone() s2)拼接后通过contains(s1)检查子串这里需要s2.clone()是因为s2后续不再被使用直接s2 s2在借用规则上不可行克隆避免了所有权转移带来的编译问题。长度比较使用len()字节长度由于比较的是两个字符串的长度是否相等字节数与字符数在此场景下判定结果一致。SwiftSolution.swiftclass Solution { func isFlippedString(_ s1: String, _ s2: String) - Bool { return (s1.isEmpty s2.isEmpty) || (s1.count s2.count (s1 s1).contains(s2)) } }Swift 实现额外处理了空字符串特例题目约束长度可为 0当s1与s2均为空串时二者互为旋转空串旋转仍是空串直接返回true。若不特判s1 s1也为空串contains(s2)对空子串的判定行为在不同实现下可能不一致显式处理更稳妥。s1.count统计的是字符个数而非字节数Swift 字符串的contains同样支持子串判定。从源码结构看实现的一致性对比上述七种实现可以发现它们在逻辑上完全同构均遵循“长度相等 拼接串包含目标串”的判定模式仅因语言 API 与所有权/可变性规则不同而在写法上略有差异语言拼接对象子串判定 API特殊处理Python3s1 * 2in短路求值长度不等不拼接Javas1 s1contains无Cs1 s1find ! npos需显式比较string::nposGos1 s1strings.Contains无TypeScripts2 s2indexOf ! -1对称写法Rusts2 s2contains需clone满足所有权规则Swifts1 s1contains空字符串特判从代码结构可以推断仓库维护者刻意保持了各语言实现的最小化与一致性所有实现都只调用一次子串检查完全契合题目“只调用一次检查子串的方法”的说明TypeScript 与 Rust 选择s2 s2的对称形式也从侧面印证了旋转关系的对称性——这一写法在语义上同样正确且优雅。边界情况与易错点总结长度不等直接返回False无需任何拼接这也是效率最高的剪枝两个空串长度均为 0 且相等s1 s1为空串此时按旋转定义空串是空串的旋转Swift 实现对此做了显式特判其余语言因contains/in对空子串的语义空串是任意串的子串自然返回true长度相等但非旋转如s1 aba、s2 babs2不是s1 s1的子串返回False子串判定 API 的返回值差异C 需与string::npos比较TypeScript 需与-1比较其他语言直接返回布尔值移植代码时需格外注意。小结面试题 01.09 字符串轮转的核心结论可浓缩为一句话长度相等时s2是s1的旋转当且仅当s2是s1 s1的子串。这一观察将看似需要多次比较的旋转问题压缩为一次子串查找时间复杂度O(n)、空间复杂度O(n)同时满足“只调用一次子串检查方法”的进阶要求。doocs/leetcode 仓库在该题目录下提供了完整的多语言实现中文题解、英文题解 及七份 Solution 源码是面试复习与多语言对比学习的优质参考。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐doocs/leetcode 题解实战面试题 01.09 字符串轮转String Rotation的双字符串拼接判定法doocs/leetcode 题解实战面试题 01.09 字符串轮转String Rotation的双字符串拼接判定法 本篇技术指南以开源仓库 doocs示例工程教程LeetCode-Book 题解精讲LeetCode 796 旋转字符串Rotate String的拼接包含判定法LeetCode Book 题解精讲LeetCode 796 旋转字符串Rotate String的拼接包含判定法 导读 LeetCode 796「旋转字示例工程doocs/leetcode 字符串处理从基础到高级的算法精解doocs/leetcode 字符串处理从基础到高级的算法精解 概述 在算法面试和编程竞赛中字符串处理是必考的核心技能之一。doocs/leetcode 项示例工程教程上一篇Velero 自定义命名空间部署指南在任意 Namespace 运行 Velero 服务器与客户端配置下一篇Kubernetes SIG Windows 2021 年度技术盘点HostProcess 容器、Windows CSI 与运维就绪之路创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考