• 作者: 作者
  • 时间:
  • 分类: 文章

前言：别把简单问题复杂化

在算法学习和求职准备的过程中，我们常常陷入一个误区：总觉得必须用上什么“高级数据结构”或者“复杂算法”才能算得上是“好解法”。比如一看到字符串匹配，脑子里蹦出来的就是 KMP、字典树（Trie）或者后缀自动机。

但事实上，在工程实践和算法竞赛中，数据规模往往是决定解题思路的关键。如果数据量很小，直接暴力往往能以最小的代码量和极高的正确率解决问题。

LeetCode 1967 题目封面

LeetCode 每日一题 —— 1967. 作为子字符串出现在单词中的字符串数目

今天要聊的 LeetCode 每日一题——1967. 作为子字符串出现在单词中的字符串数目，就是一个典型的例子。它提醒我们：简单即是美，暴力有时也是艺术。

题目回顾

题目描述非常直白：

给你一个字符串数组 patterns 和一个字符串 word。你需要统计 patterns 中有多少个字符串是 word 的子字符串，并返回这个数目。

这里需要注意一个关键定义：子字符串是字符串中的一个连续字符序列。这意味着字符必须是紧挨着的，不能跳过中间的字符（这与子序列 Subsequence 不同）。

示例：

输入：

patterns = ["a","abc","bc","d"]
word = "abc"

输出：

3

解释：

  • "a" 是 "abc" 的子字符串。
  • "abc" 是 "abc" 的子字符串。
  • "bc" 是 "abc" 的子字符串。
  • "d" 不是 "abc" 的子字符串。 所以一共是 3 个。

思路解析：从“高大上”回归“接地气”

第一反应：我想造个字典树

刚看到这道题时，我的第一反应是：这不就是多模式串匹配吗？是不是应该构建一个字典树，然后把 word 的所有可能子串提取出来去树上跑一遍？或者用 AC 自动机来搞一波？

这种想法在处理海量数据（比如 word 长度百万，patterns 数量百万）时是绝对正确的。那时候时间复杂度往往是 O(N) 或 O(N log M) 的区别，决定了是 AC 还是 TLE（超时）。

但现实是：我们往往被思维定势困住了。

审视数据范围：杀鸡焉用牛刀

让我们看看这道题的实际约束（通常此类 Easy 级别题目的约束都很宽松）。

  • patterns 的长度通常很小（比如 100 以内）。
  • 每个字符串的长度也很短。
  • word 的长度通常也在 100 以内。

在这种情况下，构建字典树的初始化开销可能比直接查找还要大！这就好比为了切个苹果，你不去拿水果刀，反而去启动了一台工业级激光切割机。虽然也能切，但太费劲了，完全没有必要。

最终策略：朴素的暴力

既然 word 和 patterns 里的元素都很短，我们直接利用高级语言内置的字符串查找函数即可。

大部分现代编程语言（Java, Python, C++, JavaScript 等）的底层字符串查找都经过了高度优化（比如使用了 Boyer-Moore 或类似的变种算法），速度极快。

算法流程：

  1. 初始化计数器 ans = 0。
  2. 遍历 patterns 数组中的每一个字符串 pattern。
  3. 调用内置函数检查 word 是否包含 pattern（即 pattern 是否为 word 的子串）。
  4. 如果包含，ans++。
  5. 返回 ans。

这个思路的时间复杂度是 O(N * M)，其中 N 是 patterns 的数量，M 是 word 的长度。在数据规模小的情况下，这个复杂度完全在可接受范围内，甚至比构建复杂结构的常数时间更优。

代码实现

这里以 Java 为例。Java 的 String 类提供了 contains() 方法，内部实现非常高效，直接拿来用即可。

class Solution {
    public int numOfStrings(String[] patterns, String word) {
        int ans = 0;
        // 遍历所有模式串
        for (String pattern : patterns) {
            // 利用系统自带的 contains 方法，既简单又快
            if (word.contains(pattern)) {
                ans++;
            }
        }
        return ans;
    }
}

代码简析：

  • 没有任何多余的数据结构定义。
  • 代码行数极少，可读性极高。
  • 几乎没有 Bug 的生存空间（除了空指针异常，但题目保证非空）。

总结与反思

这道题虽然简单，但它教给我们一个重要的编程哲学：KISS 原则。

在日常开发中，不管是做需求还是解算法题，切忌为了炫技而过度设计。当我们拿到需求时，第一步不应该是想“用什么高大上的框架”，而应该是先分析场景和数据规模。

  • 如果是 QPS（每秒查询率）极高的大数据场景，那么请务必上复杂的优化方案。
  • 如果只是内部小工具、脚本，或者数据量级很小的场景，粗暴、直接、清晰的代码永远是最好的选择。

今天这道题就是一个“降维打击”的典型案例：用最简单的 API，解决看似可以很复杂的问题。

刷题不仅仅是死磕 Hard 题道，这种 Easy 题同样能锻炼我们对问题本质的洞察力。

标签: none

评论已关闭