搜索菜单
当前位置: 首页 > Java > LeetCode字符串轮转：从O(n^2)暴力到KMP O(n)优化的完整实战

LeetCode字符串轮转：从O(n^2)暴力到KMP O(n)优化的完整实战

洛溪
洛溪
发布时间：2026-10-15 | 2人浏览过
原创

本文详细解析LeetCode字符串轮转问题，对比暴力模拟与KMP优化的效率差异，并提供Java与C++的标准实现代码，重点阐述如何通过子串拼接与模式匹配将时间复杂度降至线性。

题目要求

思路一：双指针（模拟）

该方法的核心思想是模拟所有可能的旋转位置。对于长度为 n 的字符串，共有 n 种可能的轮转起始点。我们依次以每个索引为起点，遍历整个字符串并与目标串比对。

  • 判断逻辑：外层循环确定旋转偏移量 i，内层循环逐个比对字符。利用取模运算 (i + j) % n 处理越界回绕，若所有对应字符均相等则认为匹配成功。
  • 复杂度分析：需要双重循环遍历，时间复杂度为 O(n^2)，空间复杂度为 O(1)。

Java

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length() != s2.length())
            return false;
        int n = s1.length();
        if (n == 0)
            return true;
        for (int i = 0; i < n; i++) {
            boolean res = true;
            for (int j = 0; j < n; j++) {
                if (s1.charAt((i + j) % n) != s2.charAt(j)) {
                    res = false;
                    break;
                }
            }
            if (res)
                return true;
        }
        return false;
    }
}

C++

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        if (s1.size() != s2.size())
            return false;
        int n = s1.size();
        if (n == 0)
            return true;
        for (int i = 0; i < n; i++) {
            bool res = true;
            for (int j = 0; j < n; j++) {
                if (s1[(i + j) % n] != s2[j]) {
                    res = false;
                    break;
                }
            }
            if (res)
                return true;
        }
        return false;
    }
};

思路二：子串匹配

字符串轮转的本质是一个子串匹配问题。如果字符串 s1 经过若干次轮转后等于 s2，那么 s2 必定是 s1 + s1 的子串。我们可以利用这一性质，采用更高效的匹配算法来替代暴力扫描。

手写 KMP 算法

KMP 算法通过在预处理阶段构建部分匹配表（next 数组），在匹配失败时利用已匹配的信息避免重复检查，从而将时间复杂度降为线性。以下分为 get_next 方法生成 next 数组和主匹配逻辑两部分实现。

Java - get_next

目的：构建 next 数组记录模式串的最长前后缀长度，并执行主匹配。

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length() != s2.length())
            return false;
        int n = s1.length();
        if (n == 0)
            return true;
        
        // 1. 构建 Next 数组
        int[] nxt = new int[n];
        nxt[0] = -1;
        int j = 0; // pat指针
        int k = -1; // 跳转位置
        while (j &lt; n - 1) {
            if (k == -1 || s2.charAt(j) == s2.charAt(k)) {
                if (s2.charAt(++j) == s2.charAt(++k))
                    nxt[j] = nxt[k]; // 连续相同，跳跃前缀的next
                else
                    nxt[j] = k;
            }
            else
                k = nxt[k];
        }

        // 2. 文本搜索 (txt = s1+s1)
        String txt = s1 + s1;
        j = 0;
        for (int i = 0; i &lt; 2 * n; i++) {
            if (j &lt; n &amp;&amp; txt.charAt(i) == s2.charAt(j))
                j++;
            else {
                j = nxt[j];
                if (j == -1)
                    j++;
            }
            if (j == n)
                return true;
        }
        return false;
    }
}

C++ - get_next

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        if (s1.size() != s2.size())
            return false;
        int n = s1.size();
        if (n == 0)
            return true;
        
        int nxt[n];
        nxt[0] = -1;
        int j = 0; // pat指针
        int k = -1; // 跳转位置
        while (j < n - 1) {
            if (k == -1 || s2[j] == s2[k]) {
                if (s2[++j] == s2[++k])
                    nxt[j] = nxt[k]; 
                else
                    nxt[j] = k;
            }
            else
                k = nxt[k];
        }
        
        string txt = s1 + s1;
        j = 0;
        for (int i = 0; i < 2 * n; i++) {
            if (j < n && txt[i] == s2[j])
                j++;
            else {
                j = nxt[j];
                if (j == -1)
                    j++;
            }
            if (j == n)
                return true;
        }
        return false;
    }
};

基于 DP 的自动机法

这是一种更为通用的子串匹配构建方式。它使用一个二维数组 dp[state][char]，表示在匹配了 state 个字符后，遇到新字符 char 时应跳转到的下一个状态。这种方法本质上构建了确定性有限状态自动机（DFA）。

Java - DP

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length() != s2.length())
            return false;
        int n = s1.length();
        if (n == 0)
            return true;
        
        // dp[state][char] = next_state
        int[][] dp = new int[n][256]; 
        dp[0][s2.charAt(0)] = 1;
        int x = 0; // 影子状态，用于快速计算非匹配转移
        
        for (int s = 1; s < n; s++) {
            // 先复制上一状态所有普通字符的转移
            for (int c = 0; c < 256; c++)
                dp[s][c] = dp[x][c];
            // 修正当前字符的特殊转移
            dp[s][s2.charAt(s)] = s + 1;
            // 更新影子状态
            x = dp[x][s2.charAt(s)];
        }

        String txt = s1 + s1;
        int state = 0;
        for (int i = 0; i < 2 * n; i++) {
            state = dp[state][txt.charAt(i)];
            if (state == n)
                return true;
        }
        return false;
    }
}

C++ - DP

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        if (s1.size() != s2.size())
            return false;
        int n = s1.size();
        if (n == 0)
            return true;
        
        int dp[n][256]; 
        memset(dp, 0, sizeof(dp));
        dp[0][s2[0]] = 1;
        int x = 0; // 影子状态
        
        for (int s = 1; s < n; s++) {
            for (int c = 0; c < 256; c++)
                dp[s][c] = dp[x][c];
            dp[s][s2[s]] = s + 1;
            x = dp[x][s2[s]];
        }

        string txt = s1 + s1;
        int state = 0;
        for (int i = 0; i < 2 * n; i++) {
            state = dp[state][txt[i]];
            if (state == n)
                return true;
        }
        return false;
    }
};
  • 复杂度分析：预处理构造自动机或 next 表的时间为 O(n × 字符集大小)；单次文本扫描时间为 O(n)。总体时间复杂度优于暴力法，空间复杂度为 O(n)（受限于 next 数组或 dp 表）。

调用语言内置 API

在工程实践中，直接利用标准库提供的子串查找功能是最优且最安全的做法。大多数现代语言的标准库实现底层已针对该场景做了高度优化。

Java

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        return s1.length() == s2.length() && (s1 + s1).contains(s2);
    }
}
  • 时间复杂度：O(n)（取决于底层 JDK 实现，通常为优化的 BM 或混合算法）。

C++

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        return s1.size() == s2.size() && (s1 + s1).find(s2) != string::npos;
    }
};
  • 时间复杂度：O(n)。

总结

解决字符串轮转问题时，s1 + s1 包含 s2 是核心的数学直觉。虽然调用内置 API 最为便捷，但掌握 KMP 算法及其变体（如 DP 状态机）能极大加深对模式匹配原理的理解，特别是在面试中对算法复杂度的推演和自定义实现场景下。

以上就是Java C++题解leetcode字符串轮转KMP算法详解的详细内容，更多关于Java C++ 字符串轮转KMP算法的资料请关注本站其它相关文章！

相关文章

相关标签: Java C++ LeetCode

本站声明

本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。

作者最新文章

全部内容

Python 相关产品和应用

全部下载
Python Selenium
Selenium

Selenium

4.51.0 · Windows

用于浏览器自动化和 Web 测试的 Python 工具。
Python 机器学习
scikit-learn

scikit-learn

1.9.1 · Windows

常用 Python 机器学习算法与模型评估工具库。
Python 代码质量
Black

Black

26.10.1 · Windows

强调一致性的 Python 自动代码格式化工具。
Python 代码质量
Ruff

Ruff

0.17.1 · macOS

由 Rust 编写的高速 Python 代码检查和格式化工具。
Python pytest
pytest

pytest

9.1.1 · Windows

简洁而强大的 Python 自动化测试框架。
Python FastAPI API
FastAPI

FastAPI

0.146.0 · Windows

高性能 Python API 框架，支持类型提示和自动接口文档。
Python Flask Web开发
Flask

Flask

3.1.3 · Windows

轻量灵活的 Python Web 应用框架。
Python Django Web开发
Django

Django

6.1.2 · Windows

成熟的 Python Web 框架，适合构建内容站点和业务系统。
Python Spyder
Spyder

Spyder

6.1.7 · Windows

面向科学计算与数据分析的 Python 集成开发环境。
Python SciPy
SciPy

SciPy

1.18.1 · Windows

面向科学、工程和技术计算的 Python 算法库。
Python Pandas 数据分析
pandas

pandas

3.0.6 · Windows

Python 数据分析库，提供 DataFrame 与丰富的数据处理能力。
Python NumPy
NumPy

NumPy

2.5.4 · Windows

Python 科学计算基础库，提供高性能多维数组与数值运算。

文章分类

专题列表

ipython.cn 学习网
人工智能 Java AI行业服务