题目描述

给定两个字符串 s 和 goal，如果在若干次旋转操作之后，s 能变成 goal，那么返回 true。

s 的旋转操作就是将 s 最左边的字符移动到最右边。

例如：

  • s = "abcde", goal = "cdeab" → 输出 true
  • s = "abcde", goal = "abced" → 输出 false

解题思路

本题有一个非常巧妙的技巧。

核心观察

如果我们把 s 和自己拼接起来得到 s + s，那么 s 的所有旋转结果都一定是 s + s 的一个子串。

例如 s = "abcde"：

  • s + s = "abcdeabcde"
  • 旋转 1 次："bcdea" → 是 s + s 从下标 1 开始的子串
  • 旋转 2 次："cdeab" → 是 s + s 从下标 2 开始的子串
  • 旋转 3 次："deabc" → 是 s + s 从下标 3 开始的子串
  • 旋转 4 次："eabcd" → 是 s + s 从下标 4 开始的子串

所以，s 能否通过旋转变成 goal，等价于：

  1. s 和 goal 长度相同（否则不可能通过旋转得到）；
  2. goal 是 s + s 的子串。

算法步骤

  1. 先判断 s.length() 是否等于 goal.length()，不相等直接返回 false。
  2. 将 s 拼接自身得到 s + s，使用 contains 方法检查是否包含 goal。
  3. 返回 contains 的结果。

正确性证明

设 s 的长度为 n，对 s 进行 k 次旋转（0 ≤ k < n）后得到的结果，等价于将 s 的前 k 个字符移动到末尾。这一结果恰好等于 s + s 中从下标 k 开始、长度为 n 的子串。

反过来，如果 goal 是 s + s 的子串，那么 goal 在 s + s 中的起始下标 i 一定满足 0 ≤ i < n（因为 goal 的长度也是 n），这意味着对 s 进行 i 次旋转后即可得到 goal。

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串长度。Java 中 contains 的内部实现（如 indexOf）在最坏情况下为 O(n)。
  • 空间复杂度：O(n)，拼接 s + s 需要一个长度为 2n 的字符串。

代码

1
2
3
4
5
6
7
8
package code.J796;

public class J796 {
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) return false;
        return (s + s).contains(goal);
    }
}