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

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
解释：每个模式都作为子字符串出现在单词 "ab" 中。

提示：

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

解题思路

这是一道简单的字符串匹配题目。题目要求统计有多少个模式字符串作为子字符串出现在目标单词中。

解题思路：

1. 直接遍历法（推荐）：遍历 patterns 数组中的每个字符串，使用内置的字符串搜索函数检查该字符串是否在 word 中作为子字符串出现。如果出现，计数器加一。

2. 手动匹配法：对于每个模式字符串，遍历 word 的每个位置，尝试从该位置开始匹配模式字符串。

考虑到题目的约束条件较小（字符串长度都不超过100），第一种方法既简洁又高效，是最佳选择。

各语言的实现都利用了内置的字符串查找函数：

• C++: string::find()
• Python: in 运算符
• JavaScript: includes() 方法
• C#: Contains() 方法

时间复杂度主要取决于字符串匹配算法，空间复杂度为常数级别。

代码实现

class Solution {
public:
    int numOfStrings(vector<string>& patterns, string word) {
        int count = 0;
        for (const string& pattern : patterns) {
            if (word.find(pattern) != string::npos) {
                count++;
            }
        }
        return count;
    }
};

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

public class Solution {
    public int NumOfStrings(string[] patterns, string word) {
        int count = 0;
        foreach (string pattern in patterns) {
            if (word.Contains(pattern)) {
                count++;
            }
        }
        return count;
    }
}

var numOfStrings = function(patterns, word) {
    let count = 0;
    for (let pattern of patterns) {
        if (word.includes(pattern)) {
            count++;
        }
    }
    return count;
};

复杂度分析