LeetCode 补拙笔记

0. 前言

• 日期：2026.05.25
• 题目：796. 旋转字符串
• 难度：简单
• 标签：字符串、KMP算法

1. 题目理解

问题描述： 给定两个字符串 s 和 goal，判断 s 是否可以通过若干次“将最左边字符移到最右边”的旋转操作，得到 goal。

示例：

输入：s = "abcde", goal = "cdeab" 输出：true 解释：abcde 旋转两次得到 cdeab。

输入：s = "abcde", goal = "abced" 输出：false 解释：无法通过旋转得到目标字符串。

2. 解题思路

核心观察

• 字符串 s 的所有旋转结果，都可以看作是 s + s 的一个子串。例如 abcde 的所有旋转都包含在 abcdeabcde 中。
• 解法一：直接用 contains() 判断，简单但效率取决于语言实现。
• 解法二：使用KMP算法判断子串，时间复杂度为线性级，效率更高。

算法步骤

1. 检查 s 和 goal 长度是否相等，不等直接返回 false。
2. 将 s 拼接为 s + s。
3. 判断 goal 是否是 s + s 的子串。

3. 代码实现

package lc796;

class Solution {
    public boolean rotateString(String s, String goal) {
        return s.length() == goal.length() && (s + s).contains(goal);
    }
}

4. 代码优化说明

减少冗余分支，优化KMP实现，代码更简洁紧凑：

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

    private boolean kmp(String mainStr, String pattern) {
        int[] next = getNext(pattern);
        int j = 0;
        for (int i = 0; i < mainStr.length(); i++) {
            while (j > 0 && mainStr.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            if (mainStr.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            if (j == pattern.length()) {
                return true;
            }
        }
        return false;
    }

    private int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];
        int j = 0;
        for (int i = 1; i < pattern.length(); i++) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                next[i] = ++j;
            }
        }
        return next;
    }
}

5. 复杂度分析

• contains()解法

  • 时间复杂度：$O(n)$（Java中String.contains底层为优化的暴力或Boyer-Moore算法，平均线性）
  • 空间复杂度：$O(n)$，拼接字符串的开销。

• KMP解法

  • 时间复杂度：$O(n)$，预处理next数组和匹配过程均为线性。
  • 空间复杂度：$O(n)$，next数组的开销。

6. 总结

• 核心思路：利用字符串拼接 + 子串匹配，将旋转问题转化为子串问题。
• 优化后的KMP实现，避免了内置方法的不确定性，保证了线性时间复杂度，是面试中更推荐的写法。
• 关键技巧：s+s 包含了s的所有旋转状态，这是解决这类问题的经典套路。