LeetCode 面试题 01.09. 字符串轮转

约 3 分钟
文章信息 8 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 程序员面试金典（第 6 版） 字节 微软
标签
字符串 字符串匹配

题目描述

✅ 面试题 01.09. 字符串轮转

image-20260929073544125

题意分析

判断两个字符串是否互为轮转：在一个切点把原串分为前后两段，将后段整体移到前面，两段内部顺序都不改变。最多调用一次子串检查函数。

轮转不增加或删除字符，因此长度必须相同。完全相同的字符串可以视为没有移动，两个空串也属于合法情况；只比较字符出现次数并不足够，因为轮转还保留了环形上的相对顺序。

解法：拼接包含判断

核心思路

[!blue]

将原串写成前段 x 与后段 y 的拼接，轮转结果就是 y + x。把原串重复一次得到 x + y + x + y，中间正好连续包含 y + x，所以任何合法轮转都会出现在倍长串中。

反过来，设原串长度为 n。倍长串中任意连续的 n 个字符，都是从原串某个切点开始，先取后段，再接上复制串开头的前段；因此它必定对应一种轮转。最末尾从下标 n 开始的窗口与没有轮转的原串相同。

两个方向合起来得到完整判据：先确保长度相同，再检查 s1 + s1 是否包含 s2。长度条件不能省略，否则任意较短的局部子串也可能命中，却不是完整轮转。

空串在入口直接返回真；非空等长串构造一次倍长串，再调用一次标准库包含查询，就同时检查了所有切点，无需循环生成每种轮转结果。

解题步骤

  1. 两串长度不同，返回 false。
  2. 长度相等且为空时返回 true。
  3. 构造 doubled = s1 + s1。
  4. 调用一次子串查询，返回 doubled 是否包含 s2。

代码实现

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        // 轮转不改变长度；长度相等是拼接判定的前提。
        if (s1.length() != s2.length()) {
            return false;
        }

        if (s1.isEmpty()) {
            return true;
        }

        String doubled = s1 + s1;

        // 倍长串包含所有切点对应的轮转结果。
        return doubled.contains(s2);
    }
}

import "strings"

func isFlipedString(s1 string, s2 string) bool {
    // 轮转不改变长度；长度相等是拼接判定的前提。
    if len(s1) != len(s2) {
        return false
    }
    if len(s1) == 0 {
        return true
    }

    doubled := s1 + s1
    // 倍长串包含所有切点对应的轮转结果。
    return strings.Contains(doubled, s2)
}

复杂度分析

  • 时间复杂度：设子串查询耗时为 $T(2n,n)$，总时间为 $O(n)+T(2n,n)$。若查询采用线性匹配算法，整体为 $O(n)$。
  • 空间复杂度：$O(n)$，用于构造倍长串。

关键点总结

[!green]

  • 先比较长度，否则局部子串也可能被误判为完整轮转。
  • 只拼接同一个字符串；拼接哪一侧都可以，但必须查找另一侧。
  • 标准库查询满足一次调用的要求，无需额外统计字符次数。

易错点总结

[!yellow]

  • 遗漏长度相等条件：较短子串也可能出现在倍长串中，但不属于完整轮转。
  • 拼接成 s1 + s2 再查找 s2：目标已经作为拼接的一部分存在，无法用于判断。
  • 只比较字符计数：字符总数相同只说明能重排，不能保证是移动一个切点得到的轮转。
  • 逐个切点调用包含查询：倍长串已包含全部候选，只需一次查询即可满足调用限制。

相似题目

题目 难度 关联与区别
28. 找出字符串中第一个匹配项的下标 简单 等长串的旋转判定可转为在原串拼接自身后的文本中查找目标串。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/77678642
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！