一、28. 实现 strStr()

🔗 题目链接

LeetCode 28. 实现 strStr()

📝 题目描述

给你两个字符串 haystack 和 needle，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1。当 needle 是空字符串时，返回 0。

示例：

输入：haystack = "hello", needle = "ll"
输出：2

输入：haystack = "aaaaa", needle = "bba"
输出：-1

🧠 思路分析

字符串匹配最直观的做法是暴力枚举：从 haystack 的每个字符开始，依次与 needle 比对，复杂度 O(n×m)。KMP 算法将匹配过程优化到 O(n+m)，核心思想是：匹配失败时，利用已匹配部分的信息，让模式串指针回退到某个位置继续匹配，而不是从头开始。这个回退位置由 next 数组（前缀表）决定，它记录了模式串每个位置之前的最长相等前后缀长度。比如 needle = "ababc"，当匹配到第 4 个字符 c 时发现不匹配，next[3]=2 表示可以直接从 needle[2] 继续比，因为前面的 "ab" 已经匹配上了。KMP 的难点在于理解 next 数组的构建，但代码模板背熟后，遇到字符串匹配题直接套用就行。面试中建议先讲清暴力解法，再引出 KMP 的优化思路。

💻 代码实现（C++）

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) return 0;
        
        // 构建 next 数组
        vector<int> next(m, 0);
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle[i] != needle[j]) j = next[j - 1];
            if (needle[i] == needle[j]) j++;
            next[i] = j;
        }
        
        // 匹配
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack[i] != needle[j]) j = next[j - 1];
            if (haystack[i] == needle[j]) j++;
            if (j == m) return i - m + 1;
        }
        return -1;
    }
};

📚 相关学习资源

• 文章：【必背模板】字符串匹配问题的通用解法：KMP 算法（腾讯云开发者社区·宫水三叶）—— 从题目描述到朴素解法再到 KMP，代码里注释写得很详细，适合当作模板直接背

• 文章：☆打卡算法☆LeetCode 28、实现 strStr() 算法解析（腾讯云开发者社区·恬静的小魔龙）—— 逐行分析了 next 数组的计算和匹配过程，C# 代码但逻辑清晰

免责声明：以上链接均来自公开网络。若存在侵权问题，请联系删除。

⏱ 复杂度分析

• 时间复杂度：O(n + m)，n 为 haystack 长度，m 为 needle 长度。

• 空间复杂度：O(m)，存储 next 数组。

二、459. 重复的子字符串

🔗 题目链接

LeetCode 459. 重复的子字符串

📝 题目描述

给定一个非空的字符串 s，检查是否可以通过由它的一个子串重复多次构成。

示例：

输入：s = "abab"
输出：true
解释：可由子串 "ab" 重复两次构成。

输入：s = "aba"
输出：false

🧠 思路分析

这道题有两种主流解法。第一种是暴力枚举，只需枚举长度能被 s 长度整除的子串，验证它重复若干次是否能拼成 s，复杂度 O(n√n)。第二种是 KMP 的应用：如果一个字符串由重复子串构成，那么它的最长相等前后缀（即 next 数组的最后一项）一定不等于 0，且字符串长度减去这个值得到的长度，一定能被原字符串长度整除。换句话说，如果 len % (len - next[len-1]) == 0，就说明有重复子串。这个结论的直观理解是：字符串去掉最长公共前后缀后剩下的部分，就是最小的重复单位。移动匹配法也很巧妙：把两个 s 拼起来去掉首尾，如果还能找到 s，说明 s 由重复子串构成。面试中掌握 KMP 解法更显功底，建议在理解 next 数组后再看这道题。

💻 代码实现（C++）

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        vector<int> next(n, 0);
        // 构建 next 数组
        for (int i = 1, j = 0; i < n; i++) {
            while (j > 0 && s[i] != s[j]) j = next[j - 1];
            if (s[i] == s[j]) j++;
            next[i] = j;
        }
        int len = n - next[n - 1];
        return next[n - 1] != 0 && n % len == 0;
    }
};

📚 相关学习资源

• 文章：Easy问题也值得用KMP？也许这就是算法之道！（腾讯云开发者社区·TechFlow）—— 先讲暴力枚举再引出 KMP，把前后缀匹配和重复子串之间的逻辑链条讲得非常透彻

• 文章：字符串系列⑤ —— 重复的子字符串（华为云开发者社区）—— 重点分析了 KMP 前缀表在这里的应用，用具体例子说明为什么 len - next[n-1] 就是最小周期

免责声明：以上链接均来自公开网络。若存在侵权问题，请联系删除。

⏱ 复杂度分析

• 时间复杂度：O(n)，构建 next 数组。

• 空间复杂度：O(n)，存储 next 数组。

三、139. 单词拆分

🔗 题目链接

LeetCode 139. 单词拆分

📝 题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s。字典中的单词可以重复使用。

示例：

输入：s = "leetcode", wordDict = ["leet", "code"]
输出：true
解释：返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

输入：s = "applepenapple", wordDict = ["apple", "pen"]
输出：true

🧠 思路分析

这道题用动态规划做非常直观。定义 dp[i] 表示字符串 s 的前 i 个字符组成的子串 s[0:i] 能否被拆分，dp[0] = true 表示空字符串可拆分。状态转移：遍历所有可能的分割点 j（0 ≤ j < i），如果 dp[j] 为 true 且子串 s[j:i] 在字典中，则 dp[i] = true。这一步把问题拆解成了“前 j 个字符可拆分，且从 j 到 i 这一段刚好是字典里的单词”。字典查找建议用哈希表（unordered_set）来保证 O(1) 的查找效率。这个 DP 本质上是在遍历字符串的过程中，不断检查前缀是否能与字典中的单词拼出来。如果数据量很大，可以用字典树优化，但哈希表加 DP 已经足够应对面试场景。

💻 代码实现（C++）

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

📚 相关学习资源

• 文章：LeetCode 热题100：139. 单词拆分（动态规划全解析）（阿里云开发者社区）—— 对 dp 数组的定义、状态转移和边界处理做了详细说明，还提到了用哈希集合优化查找效率

• 文章：☆打卡算法☆LeetCode 139. 单词拆分 算法解析（腾讯云开发者社区·恬静的小魔龙）—— 从“物品背包装满”的角度解释完全背包思路，适合用背包模型理解这道题

免责声明：以上链接均来自公开网络。若存在侵权问题，请联系删除。

⏱ 复杂度分析

• 时间复杂度：O(n² + m)，n 为字符串长度，m 为字典中单词总数。

• 空间复杂度：O(n + m)，dp 数组 + 哈希表。

结语

字符串匹配篇的三道题覆盖了字符串问题中最常见的几种题型：单模匹配（实现 strStr()）用 KMP 算法高效匹配；重复子串检测（重复的子字符串）考察对 next 数组的理解深度；单词拆分将问题转化为完全背包的 DP 模型。KMP 算法需要花时间理解 next 数组的含义，但一旦掌握，字符串匹配类的题目就能一通百通。单词拆分虽然归类为动态规划，但本质上也是字符串处理问题，可以用字典树优化查找效率。面试时建议先讲清楚暴力解法的局限，再引出 KMP 或 DP 的优化思路。

建议刷题顺序：先做 28 题熟悉 KMP 模板，再做 459 题深入理解 next 数组的应用场景，最后用 139 题巩固动态规划与字符串的结合。下一篇将进入 系统设计篇（LRU、LFU、Twitter 时间线等），敬请期待。

如果本文对你有帮助，欢迎点赞、收藏、转发，你的支持是我持续创作的动力 ❤️

免责声明：本文部分解题思路参考了力扣官方题解及社区优秀文章，相关链接均来自公开网络。若存在侵权问题，请联系删除。