Leetcode 每日一题详解：如何快速统计作为子字符串出现的字符串数目？

刷题是提升算法能力的必经之路，而 LeetCode 的每日一题更是大家保持手感的好办法。今天我们要聊的是第 1967 题——作为子字符串出现在单词中的字符串数目。

这道题看起来简单，但里面其实藏着不少关于字符串匹配的学问。很多初学者可能直接上手就是暴力循环，虽然能过，但有没有更优雅或者更高效的解法呢？今天我们就来掰扯掰扯。

图示：在单词中搜索 pattern 子串的过程。

题目描述

简单来说，题目给了你一个字符串数组 words 和一个字符串 pattern。你的任务是统计 words 中有多少个字符串是以 pattern 作为子字符串的。

举个例子：

• 如果 words = ["a","abc"," bc","def"]，pattern = "bc"。
• 那么只有 "abc" 和 " bc" 包含 "bc"，所以答案是 2。

思路一：直接暴力匹配（最直观的解法）

面对这种“判断 A 是不是 B 的子串”的问题，大多数编程语言其实都内置了非常强大的现成函数。

图示：KMP 算法中部分匹配表（next 数组）的构建原理。

在 Python 里，我们可以直接用 in 操作符，或者字符串的 .find() / .index() 方法；在 Java 里可以用 .contains()；C++ 也有 .find()。

解法代码

class Solution:
    def numOfStrings(self, words: List[str], pattern: str) -> int:
        count = 0
        for w in words:
            if pattern in w:
                count += 1
        return count

复杂度分析

• 时间复杂度：最坏情况下是 $O(N \cdot M \cdot L)$。其中 $N$ 是 words 的长度，$M$ 是 pattern 的长度，$L$ 是 words 中每个单词的平均长度。虽然看着大，但因为 LeetCode 的数据量通常不大，这种解法在 Python 中是可以通过的。
• 空间复杂度：$O(1)$，我们只用了常数个变量来存储计数。

优点：代码极短，写起来快，面试时能用最少的时间把结果算出来。 缺点：如果单词非常长且 pattern 也很长，底层实现的效率可能不如专业算法。

思路二：KMP 算法（进阶解法）

如果你在面试中想展示一下“硬核”功底，或者题目数据量极其变态地大，那么直接调用库函数可能就不太稳了。这时候，KMP（Knuth-Morris-Pratt）算法 就是你的不二之选。

KMP 算法的核心在于利用“部分匹配表”来避免不必要的回溯，从而将匹配效率提升到线性级别。它的优势在于当我们发现某个位置不匹配时，不需要像暴力法那样从头开始比对，而是直接跳过已知必然匹配的部分。

KMP 核心逻辑简述

1. 构建 pattern 的 next 数组（或称 pi 数组），记录 pattern 自身的重复特征。
2. 遍历 words 中的每个字符串 w，利用 next 数组进行快速匹配。

解法代码

class Solution:
    def numOfStrings(self, words: List[str], pattern: str) -> int:
        def kmp_search(text, pattern):
            if not pattern:
                return True
            # 构建 next 数组
            lps = [0] * len(pattern)
            length = 0
            i = 1
            while i < len(pattern):
                if pattern[i] == pattern[length]:
                    length += 1
                    lps[i] = length
                    i += 1
                else:
                    if length != 0:
                        length = lps[length - 1]
                    else:
                        lps[i] = 0
                        i += 1

# 开始匹配
            i = 0 # index for text
            j = 0 # index for pattern
            while i < len(text):
                if pattern[j] == text[i]:
                    i += 1
                    j += 1
                if j == len(pattern):
                    return True
                elif i < len(text) and pattern[j] != text[i]:
                    if j != 0:
                        j = lps[j - 1]
                    else:
                        i += 1
            return False

count = 0
        for w in words:
            if kmp_search(w, pattern):
                count += 1
        return count

复杂度分析

• 时间复杂度：构建 next 数组是 $O(M)$，遍历每个单词进行匹配是 $O(L)$。总复杂度为 $O(N \cdot (M + L))$。虽然常数变大，但在极端长文本下比暴力法更优。
• 空间复杂度：$O(M)$，用于存储 next 数组。

总结与建议

对于这道题来说，暴力法其实完全足够。LeetCode 的测试用例并没有刁难到强制上 KMP 的地步。

• 日常刷题/快速解题：推荐使用思路一，简洁明了，不易出错。
• 追求极致性能/学习算法：推荐实现一遍思路二，熟悉 KMP 的构建 next 数组和匹配过程，这对以后解决更复杂的字符串问题（如循环字符串匹配）非常有帮助。

不管是哪种解法，搞懂“子串匹配”这个基础动作才是关键。大家赶紧动手试一试吧！