作为子字符串出现在单词中的字符串数目

难度: Easy

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

子字符串 是字符串中的一个连续字符序列。

示例 1：

输入：patterns = ["a","abc","bc","d"], word = "abc"
输出：3
解释：
- "a" 是 "abc" 的子字符串。
- "abc" 是 "abc" 的子字符串。
- "bc" 是 "abc" 的子字符串。
- "d" 不是 "abc" 的子字符串。
patterns 中有 3 个字符串作为子字符串出现在 word 中。

示例 2：

输入：patterns = ["a","b","c"], word = "aaaaabbbbb"
输出：2
解释：
- "a" 是 "aaaaabbbbb" 的子字符串。
- "b" 是 "aaaaabbbbb" 的子字符串。
- "c" 不是 "aaaaabbbbb" 的字符串。
patterns 中有 2 个字符串作为子字符串出现在 word 中。

示例 3：

输入：patterns = ["a","a","a"], word = "ab"
输出：3
解释：patterns 中的每个字符串都作为子字符串出现在 word "ab" 中。

提示：

1 <= patterns.length <= 100
1 <= patterns[i].length <= 100
1 <= word.length <= 100
patterns[i] 和 word 由小写英文字母组成

Submission

运行时间: 25 ms

内存: 16.1 MB

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

Explain

题解采用了直接遍历的方法。对于每个patterns数组中的字符串（称为pattern），它检查该字符串是否为word的子字符串。如果是，结果计数器result增加1。最后返回result，即作为子字符串出现在word中的patterns元素的总数。

时间复杂度: O(n*m*k)

空间复杂度: O(1)

class Solution:
    def numOfStrings(self, patterns: List[str], word: str) -> int:
        result = 0  # 初始化计数器
        for pattern in patterns:  # 遍历每一个pattern
            if pattern in word:  # 检查pattern是否是word的子字符串
                result = result + 1  # 如果是，则计数器加1
        return result  # 返回计数器的值，即子字符串的数目

Explore

在word字符串非常长时，直接遍历方法的效率可能不是最优的。为了提高效率，可以考虑使用更高效的字符串搜索算法，如KMP算法、Boyer-Moore算法或Rabin-Karp算法。这些算法可以在最坏情况下提供近线性的时间复杂度，从而更有效地处理长字符串。

当前的算法实现会对patterns中的每个字符串进行检查，不论其是否重复。因此，如果patterns数组中包含重复的字符串，每个重复的字符串都会被单独计算。如果需要避免这种重复计数，可以首先使用集合（Set）来去除patterns数组中的重复元素，然后再进行子字符串的检查。

如果`pattern`的长度大于`word`的长度，那么`pattern`不可能是`word`的子字符串。在这种情况下，可以在检查之前先进行一次长度比较。如果`pattern`长度大于`word`长度，直接跳过该pattern的检查以节省时间。这种优化可以减少不必要的子字符串检查，从而提高算法效率。

该算法基本上是与字符串的编码方式无关的，因为它依赖于Python的内置字符串处理功能，这些功能良好地支持了多种编码方式，包括ASCII和Unicode。然而，在处理包含复杂字符（如表情符号或其他Unicode字符）的字符串时，需要注意字符边界和字符长度的问题，因为这些字符可能占用多个字节。这可能影响到子字符串的正确检测，特别是在跨语言或跨文化的数据处理中。